C語言堆排序經典算法TopK問題怎么解決

本文小編為大家詳細介紹“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;
    }

讀到這里，這篇“C語言堆排序經典算法TopK問題怎么解決”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。