快排的思想就是
- 寻找一个base，一般令其等于数组第一个元素
- 然后将小于等于base的数放base左边，大于的放右边
- 分别对左边的和右边的数组进行快排递归
- 最后的数组就是完成排序的
寻找第K大个数，
就是在完成快排的时候，判断当前base所在的位置和所需要的位置的情况，然后每次只快排一半就行啦。
代码实现如下：
package main
func main() {
ans := []int{1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932, 1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266, 520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744, 1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578, 798663}
}
func findKth(a []int, n int, K int) int {
//这里要做个转换
//要找第K大的，也就是要找到倒数第K个数，也就是正数第n-K+1个数
K = n - K + 1
l, r := 0, n-1
for l < r {
cur := quickSort(a[l : r+1])
//每次快排的数组长短不一，都是相对的位置，因此要加上左边界的长度，才是相对于整个数组的索引位置
cur = cur + l
if cur == K-1 {
//如果刚好是第K个数，就直接返回
return a[cur]
} else if cur > K-1 {
r = cur - 1
} else {
l = cur + 1
}
}
//最坏情况可能完成排序了，就返回那个位置
return a[K-1]
}
//快排思想如下
func quickSort(data []int) int {
n := len(data)
l, r, i := 0, n-1, 1
base := data[0]
for l < r {
if data[i] <= base {
data[i], data[l] = data[l], data[i]
i++
l++
} else {
data[i], data[r] = data[r], data[i]
r--
}
}
return r
}