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

发布时间:2023-04-19 11:20:09 作者:iii
来源:亿速云 阅读:74

本文小编为大家详细介绍“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,排序跟快排一样,从大到小排列。 那一次排序结束有三种情况:

看不懂正常,我们拿一个具体的例子来说,可以准备纸笔画一下: 原数组: [4, 6, 1, 3, 2, 7, 9, 5]

第一次遍历,取index=0为哨兵,也就是pivot=4,结束: [7 6 5 9 4 2 3 1] index为 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]

第一遍结束发现index<k-1,需要对index=4右边继续排序。

第二遍结束:[7 6 5 9 4 3 2 1]index=6,还是大于k-1=5

第三遍:遍历[left, index - 1],这个时候left=5index-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问题怎么解决”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注亿速云行业资讯频道。

推荐阅读:
  1. C语言如何实现扑克牌游戏
  2. C语言if选择结构语句怎么使用

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c语言

上一篇:C语言中分支和循环的实现形式有哪些

下一篇:C语言volatile关键字的作用是什么

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》