快捷導(dǎo)航

C語(yǔ)言堆排序經(jīng)典算法TopK問(wèn)題解析

更新時(shí)間：2023年04月10日 10:36:11 作者：Yocn

這篇文章主要為大家介紹了C語(yǔ)言堆排序經(jīng)典算法TopK問(wèn)題解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

問(wèn)題描述：

從arr[1, n]這n個(gè)數(shù)中，找出最大的k個(gè)數(shù)，這就是經(jīng)典的TopK問(wèn)題

什么是TopK，就是找到一個(gè)無(wú)序隊(duì)列中的k個(gè)最大數(shù)。 TopK的經(jīng)典算法是堆排序，這里用快排的思想解決。先上一個(gè)快排的代碼：

快速排序

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

利用快排的框架實(shí)現(xiàn)一個(gè)TopK，排序跟快排一樣，從大到小排列。那一次排序結(jié)束有三種情況：

得到的index==k-1，直接結(jié)束，返回?cái)?shù)組的前k個(gè)元素。
得到的index<k-1，這時(shí)候說(shuō)明需要的足夠大的數(shù)據(jù)還不夠，需要繼續(xù)找再小一點(diǎn)的。比如我們需要 [7,6,5]，現(xiàn)在只有 [7,6]，所以還需要找到 [5] 才可以。
得到的inedx>k-1，這時(shí)候說(shuō)明大數(shù)雖然找到了，但是不知道哪些個(gè)是最大k個(gè)。比如我們需要 [7,6,5] ，但這時(shí)候前面是**[7,4,3,5,6]**，如果直接取前三個(gè)，就會(huì)取錯(cuò)，所以還要對(duì)這些大數(shù)進(jìn)行排序。

看不懂正常，我們拿一個(gè)具體的例子來(lái)說(shuō)，可以準(zhǔn)備紙筆畫一下：原數(shù)組： [4, 6, 1, 3, 2, 7, 9, 5]

第一次遍歷，取index=0為哨兵，也就是pivot=4，結(jié)束： [7 6 5 9 4 2 3 1] index為 4.

分三種情況：

k=5，index=k-1，直接返回 [7 6 5 9 4]
k=2，也就是k<4的情況。

我們發(fā)現(xiàn)index>k-1，所以需要繼續(xù)對(duì)index=4左邊的進(jìn)行排序也就是對(duì) [7, 6, 5, 9] 進(jìn)行排序。第二次繼續(xù)取第0個(gè)為哨兵，也就是7，排序結(jié)束為 [9 7 5 6 4 2 3 1] ，index=1，這個(gè)時(shí)候index=k-1，結(jié)束，得到結(jié)果 [9, 7]

k=6，也就是k>4的情況。

第一遍結(jié)束發(fā)現(xiàn)index<k-1，需要對(duì)index=4右邊繼續(xù)排序。

第二遍結(jié)束：[7 6 5 9 4 3 2 1]，index=6，還是大于k-1=5

第三遍：遍歷[left, index - 1]，這個(gè)時(shí)候left=5，index-1=5，左右重合結(jié)束，取前6個(gè)數(shù)字為: [7 6 5 9 4 3]

三種情況分析結(jié)束，看代碼實(shí)現(xiàn)：

//返回topK
    private int[] topKort(int[] src, int left, int right, int k) {
        if (k == src.length) {
            return src;
        }
        if (left == right) {
//排序結(jié)束，取前k個(gè)數(shù)字得到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) {//繼續(xù)排序左邊的大數(shù)
            topKort(src, left, index - 1, k);
        } else if (index < k - 1) {//繼續(xù)排序右邊的小數(shù)，繼續(xù)找比較大的數(shù)
            topKort(src, index + 1, right, k);
        } else {//結(jié)束
            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語(yǔ)言堆排序經(jīng)典算法TopK問(wèn)題解析的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言堆排序TopK算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: