C語言堆排序經(jīng)典算法TopK問題怎么解決

本文小編為大家詳細(xì)介紹“C語言堆排序經(jīng)典算法TopK問題怎么解決”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C語言堆排序經(jīng)典算法TopK問題怎么解決”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。

問題描述：

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

什么是TopK，就是找到一個(gè)無序隊(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í)候說明需要的足夠大的數(shù)據(jù)還不夠，需要繼續(xù)找再小一點(diǎn)的。比如我們需要 [7,6,5]，現(xiàn)在只有 [7,6]，所以還需要找到 [5] 才可以。

• 得到的inedx>k-1，這時(shí)候說明大數(shù)雖然找到了，但是不知道哪些個(gè)是最大k個(gè)。比如我們需要 [7,6,5] ，但這時(shí)候前面是**[7,4,3,5,6]**，如果直接取前三個(gè)，就會(huì)取錯(cuò)，所以還要對(duì)這些大數(shù)進(jìn)行排序。

看不懂正常，我們拿一個(gè)具體的例子來說，可以準(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語言堆排序經(jīng)典算法TopK問題怎么解決”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。