輕鬆搞定十大排序演算法｜C++版（下）

zhuanlan.zhihu.com

4、希爾排序

演算法描述:

1959年Shell發明，第一個突破O(n2)的排序演算法，是簡單插入排序的改進版。它與插入排序的不同之處在於，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

實現邏輯:

4.0、希爾排序

(插入排序;時間A:N^1.3 , B:N^2 , E:N;空間1;不穩定)

/* (又稱縮小增量排序) 通過實驗，大量本表現出，平均時間複雜度為N^1.3*/ int gap = length; while (gap>1){ gap = gap/3 +1; for (int i = gap; i<length; i+=gap) { int current = arr[i]; int preIndex = i - gap; while (preIndex >= 0 && arr[preIndex]>current) { arr[i] = arr[preIndex]; preIndex -= gap; } arr[preIndex+gap] = current; } }

5、選擇排序

演算法描述:

選擇排序(Selection-sort)是一種簡單直觀的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

實現邏輯:

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法流程如下：

初始狀態：無序區為R[1..n]，有序區為空；

第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；

n-1趟結束，數組有序化了。

5.0、選擇排序

(選擇排序;時間A:N^2 , B:N^2 , E:N^2 ; 空間1;穩定)

for(int i =0 ;i<length-1;i++) { int minIndex =i; for(int j= i+1;j<length;j++){ if(arr[minIndex]>arr[j]){ minIndex = j; } } exchangee(arr, minIndex, i); }

6、堆排序

演算法描述:

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

實現邏輯:

將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；

6.0、堆排序

(選擇排序;時間A:NlogN,B:NlogN,E:NlogN;空間1;不穩定)

/* 堆的概念：對於大根堆，其子樹下的所有節點， 包括它自己在內的最大值為頭結點。 時間複雜度為0+log1+log2+……數學上可以證明 這個值收斂於O(N)*///向上走void heapInsert(int arr[],int index){ while (arr[index] > arr[(index-1)/2]) { exchangee(arr,index, (index-1)/2); index = (index -1)/2; }}//向下走//size為最右的邊界，size是取不到的.void heapify(int arr[],int index ,int size){ int leftChild = index*2 + 1; while (leftChild < size) { int maxChild = leftChild + 1 < size && arr[leftChild+1] >arr[leftChild] ? leftChild+1 : leftChild; int maxAll = arr[maxChild] > arr[index] ? maxChild: index; if (maxAll == index) { break; } exchangee(arr, maxAll, index); index = maxAll; leftChild = index*2 +1; }} int main(){ for(int i = 0;i <length;i++){ heapInsert(arr, i); } int size = length; exchangee(arr, 0, --size); while (size > 0){ //heapify時間複雜度為O(logN) heapify(arr, 0, size); exchangee(arr, 0, --size); } return 0;}

7、歸併排序

演算法描述:

歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。

實現邏輯:

把長度為n的輸入序列分成兩個長度為n/2的子序列；

對這兩個子序列分別採用歸併排序；

將兩個排序好的子序列合併成一個最終的排序序列。

7.0、二路歸併排序

(插入排序;時間A:NlogN,B:NlogN,E:N*logN;空間N;穩定)

/* 歸併排序內部緩存法 可以把空間複雜度降到O(1)； 歸併排序原地歸併法 也可以把空間複雜度降到O(1)但是時間復 雜度會變成O(N^2)*/void merge(int arr[],int L,int M,int R){ int* cent = new int[R - L + 1]; int i = 0; int pFirst = L; int pSecond = M+1; while (pFirst <= M && pSecond <= R) { cent[i++] = arr[pFirst] < arr[pSecond] ? arr[pFirst++]:arr[pSecond++]; } while (pFirst <= M) { cent[i++] = arr[pFirst++]; } while (pSecond <= R) { cent[i++] = arr[pSecond++]; } for (int j = 0; j < (R-L+1); j++) { arr[L+j] = cent[j]; }}void mergeSort(int arr[],int L,int R){ if (L == R){ return; } int mid = (L+R)/2; mergeSort(arr, L, mid); mergeSort(arr, mid+1, R); merge(arr,L,mid,R);}void mergeSort(int array[],int length){ if (array == nullptr || length<2) { return; } mergeSort(array,0,length - 1);}

8、計數排序

演算法描述:

計數排序不是基於比較的排序演算法，其核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。

實現邏輯:

8.0、計數排序

(計數排序;時間A:N+k,B:N+k,E:N+k;空間N+k;穩定)

/* 輸入的元素是 n 個 0到 k 之間的整數 當k不是很大並且序列比較集中時，計數排序是一個很有效的 排序演算法。 下面演算法是輸入的數組中的最小值大於等於0的情況， 可以根據需求更改。 */void countSort(int arr[] ,int length){ int max = arr[0]; int lastIndex= 0; for (int i = 1; i<length; i++) { max = arr[i]>max ? arr[i]:max; } int* sortArr = new int[max+1](); for (int j = 0; j< length; j++) { sortArr[arr[j]]++; } for (int k = 0; k<max+1; k++) { while (sortArr[k]>0) { arr[lastIndex++] = k; sortArr[k]--; } }}

9、桶排序

演算法描述:

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排）。

實現邏輯:

設置一個定量的數組當作空桶；

遍歷輸入數據，並且把數據一個一個放到對應的桶里去；

對每個不是空的桶進行排序；

從不是空的桶里把排好序的數據拼接起來。

9.0、桶排序

桶排序(時間A:N+k,B:N^2,E:N+k;空間N+k;穩定)

//桶排序是: 桶思想排序 + 一個普通的排序（常用快速排序）#pragma mark bucketSort/* 映射函數getGroupCount是得到在第幾個桶，其能保證第一 個桶有整個數組的最小值和最後一個桶有整個數組的最大值。*/int getGroupCount(long num,long size ,long min ,long max ){ int count = (int)((size)*(num - min)/(max - min)); return count;}//size 為一個桶的囊括的數的範圍void bucketSort(int arr[],int length,int size){ if (length < 2 ){ return; } int len = length; //拿到最大最小值 long min = arr[0]; long max = arr[0]; for (int i = 1 ; i<len; i++) { min = arr[i] < min ? arr[i]: min; max = arr[i] > max ? arr[i]: max; } //如果最小值等於最大值說明數組中就一種數 if (min == max) { return; } //創建桶 int bucketCount = (int)((max -min)/size +1); vector<vector<int>> bucket(bucketCount); int bid = 0; //把數組中的數 扔進桶里 for (int i =0; i < len; i++) { bid = getGroupCount(arr[i], bucketCount, min, max); bucket[bid].push_back(arr[i]); } for (int i=0; i< bucketCount; i++) { //對桶內進行插入排序。按照升序，這樣可以保證從下往上讀的穩定性 for (int j = 1; j<bucket[i].size(); j++) { if (bucket[i][j] < bucket[i][j-1]) { swap(bucket[i][j],bucket[i][j-1]); } } for (int t = 0; t< bucket[i].size(); t++) { cout<<bucket[i][t]<< ; } } // int *newArr = new int[len]; int index = 0; for (int i =0 ;i<bucketCount ;i++){ for (int j =0; j<bucket[i].size(); j++) { arr[index++] = bucket[i][j]; } } }

9.1、桶排序思想

問題描述

數組最大值問題。

給定一個無序數組，求如果排序之後，相鄰兩數的最大差值，

要求時間複雜度O（N），且要求不能用基於比較的排序。

以此題發現桶排序妙趣思想.

/* 映射函數getGroupCount是得到在第幾個桶，其能保證第一 個桶有整個數組的最小值和最後一個桶有整個數組的最大值。*/int getGroupCount(long num,long size ,long min ,long max ){ int count = (int)((size-1)*(num - min)/(max - min)); return count;}int maxGroup(int arr[],int length){ if (length < 2){ return 0; } int len = length; //拿到系統的最大值和系統的最小值 int min = INT_MAX; int max = INT_MIN; for (int i= 0; i<len; i++) { min = arr[i]<min ? arr[i]:min; max = arr[i]>max ? arr[i]:max; } if (min == max){ return 0; } int bid = 0; int* maxValue =new int[len+1]; int* minValue =new int[len+1]; bool* flag = new bool[len+1]; for (int j = 0; j<len; j++) { bid = getGroupCount(arr[j], len, min, max); minValue[bid] = minValue[bid]? (minValue[bid]<arr[j]?minValue[bid]:arr[j]):arr[j]; maxValue[bid] = maxValue[bid]? (maxValue[bid]>arr[j]?maxValue[bid]:arr[j]):arr[j]; flag[bid] = true; } int res = 0; int lastMax = 0; for (int k= 1 ; k<len+1; k++) { if (flag[k]) { res = res > (minValue[k] - maxValue[lastMax]) ? res :(minValue[k] - maxValue[lastMax]); lastMax =k; } } return res;}

10、基數排序

演算法描述:

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。

實現邏輯:

取得數組中的最大數，並取得位數；

arr為原始數組，從最低位開始取每個位組成radix數組；

對radix進行計數排序（利用計數排序適用於小範圍數的特點）；

10.0、基數排序

(基數排序;時間A:N k , B:N k , E:N * k ; 空間N+k ; 穩定)

//拿到傳入數的位數int getRadixCount(int count){ int num = 1; if (count /10 >0) { num ++; } return num;}//拿到10的傳入位數的次方(10^num)int getTenRadixCount(int radixCount){ int tenRadix = 1; while (radixCount > 0 ) { tenRadix *= 10; radixCount --; } return tenRadix;}void radixSort(int arr[], int length){ int len = length; int max = arr[0]; for (int i =1 ; i< length; i++) { max = arr[i]>max? arr[i]:max; } int radixCount = getRadixCount(max); int tenRadixCount = getTenRadixCount(radixCount); int (*bucket)[10] = new int[10][10]; int* num = new int[10](); int multiplier = 1; while (multiplier < tenRadixCount) { for (int i = 0; i< len; i++) { int curCount = arr[i]/multiplier%10; int k = num[curCount]; bucket[curCount][k] = arr[i]; num[curCount]++; } int index = 0; for (int j = 0; j < 10; j++) { if (num[j]!=0) { for (int k =0; k<num[j]; k++) { arr[index++] = bucket[j][k]; } } //把桶清空，準備下一次循環。 num[j] = 0; } multiplier *= 10; }}

更多筆經面經：https://www.nowcoder.com/discuss?type=2&order=0