本文小编为大家详细介绍“C语言堆排序经典算法TopK问题怎么解决”,内容详细,步骤清晰,细节处理妥当,希望这篇“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; }