? ? 今天在一個OJ上做了一個叫“Advanced Heap Sort”的題，題的解決算法沒什么難的，但是對時間復雜度有要求，用正常的算法實現，都會超時，所以我就把這個題拿過來分享一下。

問題：

題目內容： 有兩個序列S1和S2，各有N個元素。當我們在S1,S2各取一個數字時，總共會有N*N這么多可能的”和”(sum)。請找出這N*N這么多和里最小的N個值，并將它們加總后輸出。輸入格式: 只有一筆測資。測試資料第一行為一個正整數N。第二行有N個數字，以空白隔開，代表序列S1。第二行有N個數字，以空白隔開，代表序列S2。數字范圍： 0 < N < 10000輸出格式： 輸出一行，N個最小的可能的和的加總。輸入樣例： 5 1 3 5 7 9 2 4 6 8 10輸出樣例： 27時間限制：100ms內存限制：128000kb

算法分析：

? ? 這個題目既然是要求用堆排序，所以首先想到的時，建立一個N2的數組，通過兩層循環，將所有的結果和填寫到N2的大數組中，然后通過最小堆排序，將前N個進行和運算就可以了。但是這個題N的范圍到10000，所以堆的大小是100000000，那么這個算法的時間復雜度就是O(n2)+ O(nlogN)+ O(nlogN) + O(n)，可見時間復雜度和空間復雜度都很高，不能滿足題目要求。

? ? 所以，這里需要先將兩個數列時行從小到大的排序，然后，建立一個N大的固定的堆，先填入N的數，并經進行最大堆排序，排序完成后，結果也就出來了。這里還有一個關鍵就是往堆里插入的值，原來是要插入N2個，因為現在將兩個數列進行了從大到小的排序，所以滿足插入的數列為：從第一個數組元素到(N/1) + (N/2) + (N/3) + .... + (N/N)? 【因為A[1] + B[i], 0 <= i <= (N-1)/2都是答案的話（也就是前N小的），那么，A[0] + B[i]也是答案。因為A[0] + B[i] <= A[1] + B[i]】?，通過這種方式進行時間復雜度的提升，再就是在進行兩個數列的排序時，要使用歸并法時行排序。

? ? 這樣的話，空間復雜度是N，時間復雜度是O(N log N) +?O(log N) +?O(NlogN * logN) +?O(N log N)，提升了不少，通過測試，完勝。

算法代碼：

#include <stdio.h>int arrRst[10000]; //堆 int arrMer[10000]; //歸并排序的臨時數組 int n = 0; // 堆游標 //歸并函數 void merge(int *arr, int start, int mid, int end){int i, j, k;i = k = start;j = mid + 1;while((i <= mid) && (j <= end)){if(arr[i] <= arr[j]){arrMer[k++] = arr[i++];}else{arrMer[k++] = arr[j++];}}while(i <= mid){arrMer[k++] = arr[i++];}while(j <= end){arrMer[k++] = arr[j++];}for(i = start; i <= end; i++){arr[i] = arrMer[i];} }//歸并函數 void mergeSort(int *arr, int start, int end){int mid;if(start < end){mid = (start + end) / 2;mergeSort(arr, start, mid);mergeSort(arr, mid + 1, end);merge(arr, start, mid, end);} }void swap(x, y){int t;t = arrRst[x];arrRst[x] = arrRst[y];arrRst[y] = t; }void shiftDown(int x){int t, flag = 0;while(x * 2 <= n && flag == 0){//左孩子 if(arrRst[x * 2] > arrRst[x]){t = x * 2;}else{t = x;}//右孩子if(x * 2 + 1 <= n){if(arrRst[x * 2 + 1] > arrRst[t]){t = x * 2 + 1;}} if(t == x){flag = 1;}else{swap(x, t);x = t;}} }void creatHeap(){int i;for(i = n / 2; i >= 1; i--){shiftDown(i);} }int main(){int arr[10000], arr2[10000];int N, sum = 0;int i, j;//輸入 scanf("%d", &N);for(i = 1; i <= N; i++){scanf("%d", &arr[i]);}for(i = 1; i <= N; i++){scanf("%d", &arr2[i]);}//排序mergeSort(arr, 1, N);mergeSort(arr2, 1, N); for(i = 1; i <= N; i++){for(j = 1; j <= N / i; j++){//要插入的數據 if(n <= N - 1){ //只存放前N個 arrRst[++ n] = arr[i] + arr2[j];if(n == N){creatHeap();//對前N個建立最大堆 } }else{if(arr[i] + arr2[j] < arrRst[1]){arrRst[1] = arr[i] + arr2[j];shiftDown(1);}} }}for(i = 1; i <= n; i ++){sum += arrRst[i];}printf("%d", sum);return 0; }

博客名稱：王樂平博客
博客地址：http://blog.lepingde.com
CSDN博客地址：http://blog.csdn.net/lecepin

總結

以上是生活随笔為你收集整理的高级堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。