排序演算法是一類比較基礎的演算法，也是在學習編程與演算法的程序中必須學習的一類問題，初學者經常在排序時摸不著頭腦，面對一眾的排序，不知從何處下手，下面筆者將以筆記的形式分享一下我在學習演算法時整理的一些排序演算法，
假設現有亂序陣列：5, 2, 7, 4, 6, 1, 8, 我們將其排序為升序陣列，各種方法程序如下：
1.冒泡排序，
冒泡排序是最簡單的一種排序手段，也是新手最容易想到的一種演算法，它通過每一項與其后面的每一項依次比較，找到最大（最小）值并交換位置，經過一次遍歷，即可將陣列排序，其程序大致如下：
首先提取第一個元素5, 與它后面每一項進行比較，找到最小項1，并與其交換位置，得到陣列：1, 2, 7, 4, 6, 5, 8，
隨后的第二個元素2, 經比較后發現沒有比2更小的項，陣列不變，
再依次提取7, 4, 6, 5，分別與它們后面的每一項進行對比，找到最小項并交換位置，最終陣列將按照升序排序，即1, 2, 4, 5, 6, 7, 8，
其代碼如下：
1 for (int i = 0; i < n - 1; i++) 2 for (int j = i + 1; j < n; j++) 3 if (arr[i] > arr[j]) 4 { 5 int tmp = arr[i]; 6 arr[i] = arr[j]; 7 arr[j] = tmp; 8 }
由執行程序可以看到，冒泡排序執行中需要雙層嵌套回圈，一旦需要排序的陣列過長，其效率也隨之迅速降低，
在日常使用中，筆者僅在小型陣列的排序中使用這種演算法，因為其代碼簡單直接，工程量比較小，代碼也易于維護，
2.并歸排序，
并歸排序采用的是分治思想，利用函式的遞回，將龐大的排序問題逐級化簡，最后并歸得到有序的陣列，它的思想是將一個陣列一分為二，再將兩個子陣列分別排序，再依次比較陣列的首項，將較小值依次放入原陣列中，最終得到有序陣列，其程序大致如下：
首先將陣列拆分為array1：5, 2, 7, 4, 和array2：6, 1, 8, 分別對這兩個陣列進行排序：array1：2, 4, 5, 7, 和array2：1, 6, 8，
再將兩個陣列并歸為一個陣列：首先比較兩個陣列的首項：由于1 < 2，將array2中的1提取，歸入原陣列，再比較兩個陣列的首項：由于2 < 6，本次提取值為2，，，以此類推，同時，為了防止陣列發生越界問題，需要在陣列末項之后人為添加一個無窮項，保證該項大于陣列中的每一項，從而防止陣列越界的現象發生，經過并歸程序后，原陣列排序完成，
但是這里會引出一個問題，該如何排序這兩個子陣列呢？這里便需要用到遞回的思想，我們可以讓函式呼叫它自身從而完成對拆分開來的子項的排序，
但這樣又會產生接下來的問題，該如何控制遞回結束？這里由于最后無窮項的存在，當陣列長度為2時，陣列內有效值便只有一個，在此時，遞回結束，將這項回傳，交由函式下面的內容完成并歸操作，
其代碼如下：
1 void merge(int* arr, int n) //由于采用指標傳遞的方式，函式將直接對原地址進行操作，故函式被定義為無回傳值 2 { 3 if (n > 1) //筆者的函式傳遞的n是陣列長度，當陣列長度大于1,陣列可以被繼續拆分，繼續遞回若等于1,無法拆分，遞回結束 4 { 5 int* arr1 = new int[n / 2 + n % 2 + 1], * arr2 = new int[n / 2 + 1]; //開辟新陣列，為了添加無窮項防止越界，每一個陣列長度增加1位 6 for (int i = 0; i < n / 2 + n % 2; i++) 7 arr1[i] = arr[i]; 8 arr1[n / 2 + n % 2] = 100; //筆者代碼排序的陣列最小項為0, 最大項為99, 故將無窮項設定為100 9 for (int i = n / 2 + n % 2; i < n; i++) 10 arr2[i - n / 2 - n % 2] = arr[i]; 11 arr2[n / 2] = 100; 12 merge(arr1, n / 2 + n % 2); //遞回排序子陣列 13 merge(arr2, n / 2); 14 for (int i = 0, j = 0, k = 0; i < n; i++) //將兩個子陣列并歸 15 if (arr1[j] <= arr2[k]) 16 { 17 arr[i] = arr1[j]; 18 j++; 19 } 20 else 21 { 22 arr[i] = arr2[k]; 23 k++; 24 } 25 } 26 delete[] (arr1); //釋放由new申請的記憶體
27 delete[] (arr2);
28 }
并歸排序采用了遞回的方式，由于無需雙重回圈，其執行效率相較冒泡排序在處理長陣列時有所提升，但是由于其代碼相對復雜，筆者在日常使用中不常使用這種演算法，
3.堆排序，
堆排序利用了堆的性質，通過維護一個最大堆或最小堆，提取堆頂元素放入原陣列完成排序，
這里首先要理解二叉堆的性質：二叉堆是一個陣列，可以近似為一個完全二叉樹，
如圖為一個最大堆，a為展開為樹的形態，b為陣列形態，由堆的對應關系容易得到，任意節點的下標除以2即可得到其父節點的下標，而父節點下標乘2可獲得子節點的左節點，乘2加1可獲得右節點，而這個最大堆的根是最大值，
若要維護堆的性質，需要自上而下比較，找到父節點與兩個子節點中的最大項，將最大的值與父節點交換位置，直到到堆的底層結束，
而建立堆的程序就是對堆的每一個節點執行維護堆的程序，而每次取出根節點，便需要重新執行維護堆，以確保堆始終為最大堆，
其代碼如下：
1 void heap(int* arr, int n) //利用堆進行排序，筆者傳值方式采用指標，無回傳值 2 { 3 for (int i = n / 2; i >= 0; i--) //建堆，自下而上對每一個非底層節點執行維護，確保最終得到最大堆 4 heapify(arr, i, n); 5 for (int i = n - 1; i >= 1; i--) //依次取出堆頂最大值，插入陣列末端 6 { 7 int tmp = arr[i]; //用堆底層值替換掉頂層值，從而取出頂層值 8 arr[i] = arr[0]; 9 arr[0] = tmp; 10 heapify(arr, 0, --n); //由于取出最大值后，堆被破壞，重新維護，而此時需要維護的堆長度應該減1,因為末項已經是我們需要的值，因此從堆中剔除 11 } 12 } 13 14 void heapify(int* arr, int n, int size) //維護堆的性質 15 { 16 int largest, l, r; //分別為最大的節點，左節點，右節點 17 l = n * 2; 18 r = n * 2 + 1; 19 if (l < size && arr[l] > arr[n]) //兩次判斷，比較出三個節點中最大值的下標 20 largest = l; 21 else 22 largest = n; 23 if (r < size && arr[r] > arr[largest]) 24 largest = r; 25 if (largest != n) //如果父節點不是最大值，交換最大值到父節點，重新維護子節點所在分支堆的性質 26 { 27 int tmp = arr[n]; 28 arr[n] = arr[largest]; 29 arr[largest] = tmp; 30 heapify(arr, largest, size); 31 } 32 }
堆排序同樣利用了遞回的思想，效率相對較高，其主要時間消耗在建堆的程序，后期僅需要回圈取值，重新維護堆即可，但是堆排序亦或是建堆，可以用于決策演算法等其它演算法，這是堆的獨特優勢，因此我們在大型專案可以重復利用建堆代碼，發揮其獨到優勢，減少工程量，
4.快速排序，
快速排序，顧名思義它是排序速度最快的排序方式，它也利用了遞回的思想，同并歸排序類似，它通過將陣列一分為二，兩側分別排序，從而達到排序的目的，但與并歸不同的是，快速排序沒有后期并歸的程序，在拆分陣列的程序中，快速排序可以做到一側的最大值小于另一側的最小值，故最后無需比較，直接連接即可，其思想如下：
首先取陣列末尾值為中間值，對陣列前面的所有值依次比較，小于該中間值的向前移動，大于的向后移動，即，當一個值小于中間值，它會與大于中間值部分的下標最小的值進行交換，同時令大于中間值部分的下標加一，實作大于中間支部分的移動，而當一個值大于中間值時，將大于中間值部分擴張包含該值即可，當大于中間值部分移動到中間值處，將中間值移動至兩個子陣列之間，至此，中間值左側所有值都小于中間值，中間值右側所有值都大于中間值，將中間值兩側的陣列再次分別排序，直到陣列不可在分，排序結束，
其代碼如下：
1 void quick(int* arr, int m, int n) //快速排序遞回部分 2 { 3 if (m < n) 4 { 5 int i = partition(arr, m, n); //每次遞回尋找中間值下標，再依次遞回中間值左側與右側部分 6 quick(arr, m, i - 1); 7 quick(arr, i + 1, n); 8 } 9 } 10 11 int partition(int* arr, int m, int n) //快速排序處理陣列部分 12 { 13 int x = arr[n]; //陣列末尾值作為中間值 14 int i = m - 1; //i用于小于中間值部分下標的計數 15 for (int j = m; j < n; j++) //遍歷陣列，將值歸檔 16 { 17 if (arr[j] <= x) //對大于中間值的值的處理 18 { 19 i++; 20 int tmp = arr[i]; 21 arr[i] = arr[j]; 22 arr[j] = tmp; 23 } 24 } 25 int tmp = arr[i + 1]; //將中間值插入兩個子數列之間 26 arr[i + 1] = arr[n]; 27 arr[n] = tmp; 28 return i + 1; //回傳中間值 29 }
快速排序是運行效率極高的一種排序演算法，在處理大型陣列時極其有效，而且演算法消耗的記憶體少，適合對性能有要求的專案，當然，對于小型陣列的排序很難體現快速排序的優越性，微小型陣列排序更多還是冒泡等相對簡單的排序比較方便開發，
5.線性時間排序，
線性時間排序是一類特殊的排序演算法，這類演算法不是簡單的依賴比較陣列元素的大小，而是巧妙地利用陣列的下標對其進行排序，其時間消耗隨著需要排序的陣列的特點會有所變化，有時效率會很高，甚至超過快速排序，而有時效率則一般，但是這類演算法普遍的特點是會有記憶體消耗，記憶體的開銷會大于快速排序，因此僅適用于特定資料的排序，不如快速排序普適，
計數排序
計數排序適用于一個連續正整數陣列，陣列的連續性越強，其效率也就越高，
計數排序巧妙地將陣列的元素當作陣列下標，開辟一個新陣列，利用陣列元素充當新陣列的下標，利用新陣列的值來計數，最后直接將新陣列的下標從小到大按統計的數量輸出，完成排序，
其代碼如下：
1 void count(int* arr, int n) 2 { 3 int max = arr[0]; 4 for (int i = 1; i < n; i++) //找出陣列最大值 5 if (arr[i] > max) 6 max = arr[i]; 7 max++; 8 int* tmp = new int[n]; 9 int* count = new int[max]; 10 for (int i = 0; i < max; i++) //陣列初始化 11 count[i] = 0; 12 for (int i = 0; i < n; i++) //將陣列下標用于計數 13 count[arr[i]]++; 14 for (int i = 1; i < max; i++) //統計每個下標的排位 15 count[i] += count[i - 1]; 16 for (int i = n - 1; i > 0; i--) //重新寫回原陣列 17 { 18 tmp[count[arr[i]]] = arr[i]; 19 count[arr[i]]--; 20 } 21 for (int i = 0; i < n; i++) 22 arr[i] = tmp[i]; 23 delete[] (tmp); //釋放空間 24 delete[] (count); 25 }
基數排序：
基數排序同樣適用于連續正整數陣列，與計數排序不同的是，基數排序陣列最大值位數越低，其排序效率越高，
基數排序也是將陣列元素作為下標，依次統計在每一位上的資料的數量，經過多次回圈排序統計后，可以得到有序陣列，
其代碼如下：
1 void radix(int* arr, int n) 2 { 3 int max = arr[0]; //找到最高為位數 4 for (int i = 1; i < n; i++) 5 if (arr[i] > max) 6 max = arr[i]; 7 int digit = 0; 8 while (max > 10) 9 { 10 max /= 10; 11 digit++; 12 } 13 int* tmp = new int[n]; //用于存盤中間資料 14 int* count = new int[10]; //用于位數的統計 15 for (int i = 0, radix = 1; i <= digit; i++, radix *= 10) 16 { 17 for (int j = 0; j < 10; j++) //初始化統計陣列 18 count[j] = 0; 19 for (int j = 0; j < n; j++) //位數數量統計 20 { 21 int k = (arr[j] / radix) % 10; 22 count[k]++; 23 } 24 for (int j = 1; j < 10; j++) 25 count[j] += count[j - 1]; 26 for (int j = n - 1; j >= 0; j--) //將一輪排列的值寫入中間陣列 27 { 28 int k = (arr[j] / radix) % 10; 29 tmp[count[k] - 1] = arr[j]; 30 count[k]--; 31 } 32 for (int j = 0; j < n; j++) //將中間陣列值寫回 33 arr[j] = tmp[j]; 34 } 35 delete[] (tmp); //釋放空間 36 delete[] (count); 37 }
以上就是筆者最近統計的一些排序演算法，同時筆者也在不斷學習其它的演算法，歡迎指正，
（演算法參考自《演算法導論（原書第三版）》--機械工業出版社）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79583.html
標籤：其他
上一篇：跟我一起學演算法——二項堆
下一篇：不相交集類及其應用生成迷宮