C语言堆排序经典算法TopK问题怎么解决

栏目分类：其他教程    发布日期：2023-10-24    浏览次数：315次     收藏

本文小编为大家详细介绍“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

index=1

index=k-1

• 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

三种情况分析结束，看代码实现：

//返回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;
    }