C语言堆排序经典算法TopK问题解析
问题描述：
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题
什么是TopK，就是找到一个无序队列中的k个最大数。 TopK的经典算法是堆排序，这里用快排的思想解决。 先上一个快排的代码：
快速排序
private void quickSort1(int[] src, int left, int right) {
if (left == right) return;
int index = sort1(src, left, right);
quickSort1(src, left, index - 1);
quickSort1(src, index + 1, right);
}
private int sort1(int[] src, int start, int end) {
int left = start;
int right = end;
int pivot = start;
while (left < right) {
if (src[right] < src[pivot]) {
if (src[left] > src[pivot]) {
swap(src, left, right);
} else {
left++;
}
} else {
right--;
}
}
swap(src, pivot, left);
return left;
}
TopK
利用快排的框架实现一个TopK，排序跟快排一样，从大到小排列。 那一次排序结束有三种情况：
- 得到的
index==k-1，直接结束，返回数组的前k个元素。 - 得到的
index<k-1，这时候说明需要的足够大的数据还不够，需要继续找再小一点的。比如我们需要 [7,6,5]，现在只有 [7,6]，所以还需要找到 [5] 才可以。 - 得到的
inedx>k-1，这时候说明大数虽然找到了，但是不知道哪些个是最大k个。比如我们需要 [7,6,5] ，但这时候前面是**[7,4,3,5,6]**，如果直接取前三个，就会取错，所以还要对这些大数进行排序。
看不懂正常，我们拿一个具体的例子来说，可以准备纸笔画一下： 原数组： [4, 6, 1, 3, 2, 7, 9, 5]
第一次遍历，取index=0为哨兵，也就是pivot=4，结束： [7 6 5 9 4 2 3 1] index为 4.
分三种情况：
- k=5，
index=k-1，直接返回 [7 6 5 9 4] - k=2，也就是k<4的情况。
我们发现index>k-1，所以需要继续对index=4左边的进行排序也就是对 [7, 6, 5, 9] 进行排序。 第二次继续取第0个为哨兵，也就是7，排序结束为 [9 7 5 6 4 2 3 1] ，index=1，这个时候index=k-1，结束，得到结果 [9, 7]
- k=6，也就是
k>4的情况。
第一遍结束发现index<k-1，需要对index=4右边继续排序。
第二遍结束：[7 6 5 9 4 3 2 1]，index=6，还是大于k-1=5
第三遍：遍历[left, index - 1]，这个时候left=5，index-1=5，左右重合结束，取前6个数字为: [7 6 5 9 4 3]
三种情况分析结束，看代码实现：
//返回topK
private int[] topKort(int[] src, int left, int right, int k) {
if (k == src.length) {
return src;
}
if (left == right) {
//排序结束，取前k个数字得到result
int[] result = new int[k];
System.arraycopy(src, 0, result, 0, k);
return result;
}
//获取一次排序哨兵的位置
int index = sortBig(src, left, right);
if (index > k - 1) {//继续排序左边的大数
topKort(src, left, index - 1, k);
} else if (index < k - 1) {//继续排序右边的小数，继续找比较大的数
topKort(src, index + 1, right, k);
} else {//结束
int[] result = new int[k];
System.arraycopy(src, 0, result, 0, k);
return result;
}
return new int[k];
}
//从大到小排序 快排思想
private int sortBig(int[] src, int left, int right) {
int pivotIndex = left;
int pivot = src[pivotIndex];
left++;
while (left < right) {
if (src[right] > pivot) {
if (src[left] < pivot) {
swap(src, left, right);
} else {
left++;
}
} else {
right--;
}
}
swap(src, pivotIndex, left);
return left;
}以上就是C语言堆排序经典算法TopK问题解析的详细内容，更多关于C语言堆排序TopK算法的资料请关注其它相关文章！
相关文章