幾種常見的排序演演算法總結
常見的幾種排序演演算法
排序演演算法有很多，比較常見的有：氣泡排序、選擇排序、插入排序、希爾排序、歸併排序、快速排序、堆排序、計數排序、桶排序、基數排序等。並不是所有的都需要會。
本文只會對其中部分演演算法進行總結。
氣泡排序
氣泡排序是一種比較簡單的排序方法。也比較好理解，但是通常情況下效能不是很好。在氣泡排序中，序列中的每個資料就是水中的泡泡一樣，一個個的向上冒出來，直到冒出水面（達到最大位置）。
（PS：此處說的是從小到大排序，而從大到小排列只需要換個思路）
演演算法步驟
1、從開頭到結尾遍歷陣列，比較相鄰的元素。如果前一個比後一個大，就交換他們兩個。
point
|
nums = [4,35,23,34,5,4]
// point 此時發現 nums[point] 比 nums[point + 1] 小，調換他倆的位置。
2、對每一個相鄰的資料進行對比，直到序列結尾的最後一對，此時「最大值」已經被移動到了「最後一個位置」。
point
|
nums = [4,23,34,5,35,4]
// 當 point 到達倒數第二個位置，此時發現 nums[point] 比 nums[point + 1]小
// 調換她倆位置後，就把 35 放到了最後一個，此時最大值已經找出。
3、重複 1和2 操作。但是每次做完 1和2 操縱後，需要遍歷的數就少一個（最後一個），因為每次都會有一個最大值已經被排好了放到了最後。
實現
Java 實現
public class BubbleSort {
public static void main(String[] args) {
int[] nums = {12,123,432,23,1,3,6,3,-1,6,2,6};;
sort(nums);
System.out.printf("finish !");
}
public static void sort(int[] nums){
int temp ;
for(int len = nums.length ; len > 0; len --){
// 第一層遍歷 len 是需要排序的陣列長度。
for(int i = 0 ; i < len - 1 ; i++){
// 第二層遍歷，遍歷的資料，每次都少一。
// 但是每次都會把一個最大值放到最後 nums[len - 1] 的位置。
if(nums[i] > nums[i + 1]){
temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
}
}
}
選擇排序
選擇排序是一種直觀的排序方法。他和氣泡排序一樣，需要多次遍歷序列。不過氣泡排序，是將最大值挨個的替換相鄰資料（冒泡）的方式最後放到最大值的位置的。而選擇排序，通過一個指標（point），標記了最大值所在的索引位置。當遍歷到最後的時候，將標記的最大值所在的位置與最後一個數交換。
演演算法步驟
1、從頭到尾的遍歷數列，遍歷過程中，用一個指標記錄最大值（最小值）所在的位置。
2、將最大值所在位置的資料與最後一個交換。
3、重複 1和2 步，每次重複後，需要遍歷的數列長度就減 1。
實現
Java 版
public class SelectionSort {
public static void main(String[] args) {
int[] nums = {12,123,432,23,1,3,6,3,-1,6,2,6};;
sort(nums);
System.out.printf("finish !");
}
public static void sort(int[] nums){
int max ; // 最大數所在的位置。
int temp;
for(int len = nums.length ; len > 0; ){
max = 0;
for(int i = 0 ; i < len ; i++){
if(nums[i] > nums[max]){
max = i;
}
}
temp = nums[max];
nums[max]= nums[len - 1];
nums[ --len] = temp;
}
}
}
我們發現，選擇排序每次找最大值的時候，都要遍歷剩下的所有元素。我們有什麼方法可以優化每次查詢最大（最小）值的速度呢？後面會講到的「堆排序」就是為了優化查詢最大值的。
插入排序
插入排序的思想是將一個待排序的元素，插入到一個已經排序好的元素的指定位置。比如我們打撲克牌的時候，每次拿到一張牌，我們會將他插入到手中已經排好順序的手牌中，這樣當我們拿到所有的撲克牌後，手中自然就有序了。
對比到到具體的程式設計中，我們可以用一個指標將一個序列分割成左右兩部分，左邊認為是已排序號（手中的牌），右邊每次取一個放到左邊的序列中。
演演算法步驟
有如下陣列：[9,3,4,2]
1、用一個指標 i ，指向陣列的 1 的位置。此指標將陣列分為左右兩邊 [9] 和 [3,4,2]。此時左邊只有一個數，所以是有序的，右邊是無序的。
i
|
[9,3,4,2]
2、將 3 依次與前面有序的數對比，如果比前面的數小，就將兩個位置上的數交換直到把 i 位置的數放到正確的位置。
i
|
[9,3,4,2]
此時nums[i] < nums[i-1]，交換兩個數。
[3,9,4,2]
3、將 i 向後移一位，然後重複 2操作。
i
|
[3,9,4,2]
實現
Java 版
public class InsertSort {
public static void main(String[] args) {
int[] nums = {5,1,4,6,2,66,-1,34,-9,8};
sort(nums);
System.out.println("finish!");
}
public static void sort(int[] nums){
for(int i = 1 ; i < nums.length ; i++){
for(int j = i ; j > 0; j--){
if(nums[j] < nums[j - 1]){
swap(nums,j,j - 1);
}else{
break;
}
}
}
}
public static void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
插入排序有一個優化版本「希爾排序」，本文中就不詳細講了，感興趣的可以去搜一下。
歸併排序
要將一個陣列排序，可以先將它分成兩半分別排序，然後再將結果合併（歸併）起來。這裡的分成的兩半，每部分可以使用其他排序演演算法，也可以仍然使用歸併排序（遞迴）。
我看《演演算法》這本書裡對歸併演演算法有兩種實現，一種是「自頂向下」，另一種是「自底向上」。這兩種方法，個人認為只是前者用了遞迴的方法，後者使用兩個 for 迴圈模擬了遞迴壓棧出棧的演演算法，本質上還是相同的（如果理解錯誤，還望大佬指出）。
演演算法步驟
1、將要排序的序列分成兩部分。
2、將兩部分分別各自排序。然後再將兩個已經排序好的序列「歸併」到一起，歸併後的整個序列就是有序的。
3、將兩個有序的序列歸併的步驟：
3.1、先申請一個空間，大小足夠容納兩個已經排序的序列。
3.2、設定兩個指標，最初位置分別為兩個已經排序序列的起始位置。
3.3、比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置。
3.4、重複3.3 步驟。
歸併排序，比較重要的是「分治」思想和「歸併」的操作。
歸併操作，是將兩個「有序」的序列，合併成一個有序的序列的方法。而這兩個有序的序列，又是根據「分治」思想將一個學列分割成的兩部分（將一個序列不斷的分隔，到最後就剩一個的時候他自然就是有序的）。
實現
Java 版
public class MergeSort {
public static void main(String[] args) {
int[] nums = {12,123,432,23,1,3,6,3,-1,6,2,6};;
sort(nums,0,nums.length -1);
System.out.printf("finish!");
}
public static void sort(int[] nums,int left,int right){
if(left >= right){
return;
}
// 遞迴的將左半邊排序
sort(nums,left,right - left / 2 - 1);
// 遞迴的將右半邊排序
sort(nums,right - left / 2 ,right);
// 此時左右半邊都分別各自有序，再將其歸併到一起。
// 如：[1,9,10 , 3,7,8]
merge(nums,left,right - left / 2,right);
}
// 此方法叫做原地歸併，將陣列 nums 根據 mid 分隔開，左右看作是兩個陣列。
// 類似於 merge(int[] nums1,int[] nums2)，將 nums1 和 nums2 歸併
public static void merge(int[] nums ,int left,int mid,int right){
int i = left,j = mid;
int[] temp_nums = new int[nums.length];
for(int key = left ; key <= right; key++)
// 將原來陣列複製到臨時陣列中。
temp_nums[key] = nums[key];
for(int key = i ; key <= right; key++){
if(i > mid){
nums[key] = temp_nums[j++];
} else if (j > right) {
nums[key] = temp_nums[i++];
} else if (temp_nums[i] > temp_nums[j]) {
nums[key] = temp_nums[j++];
}else{
nums[key] = temp_nums[i++];
}
}
}
}
快速排序
快速排序是一種分治的排序演演算法，它將一個陣列分成兩個子陣列，將兩部分獨立的排序
快速排序可能是應用最廣泛的排序演演算法了。快速排序流行的原因是它實現簡單、適用於各種不同的輸入資料且在一般應用中比其他排序演演算法都要快得多。——《演演算法（第四版）》
演演算法步驟
- 從數列中挑出一個元素，稱為 "基準"（pivot）;
- 所有元素比"基準"值小的擺放在前面，所有元素比"基準"值大的擺在後面，相同的數可以到任一邊。這個稱為分割區（partition）操作。
- 遞迴地（recursive）使用同樣的方法把小於基準值元素的子數列和大於基準值元素的子數列排序；
演演算法過程
1、給定一個亂序的陣列
[5,1,4,6,2,66,34,8]
2、選擇第一個為基準數，此時把第一個位置置空。兩個指標，left從左到右，找比 piovt 「大」的數；right 從右向左，找比 piovt 「小」的數。
left right
| |
[_,1,4,6,2,66,34,8]
|
piovt = 5
3、right 從右向左（<-），找比 piovt 「小」的數 2。
left right
| |
[_,1,4,6,2,66,34,8]
|
piovt = 5
4、left從左到右（->），找到了比 piovt 大的數 6。
left right
| |
[_,1,4,6,2,66,34,8]
|
piovt = 5
5、此時將 left 和 right 上的數對調。
left right
| |
[_,1,4,2,6,66,34,8]
|
piovt = 5
6、right 繼續向左查詢，直到 left = right。（正常情況下要重複 4、5 步驟多次才會得到 left = right）
此時將 left 位置的數放到原來 piovt 位置上，將 piovt 放到 left 位置上。
left
right
|
[2,1,4,5,6,66,34,8]
- -
|
piovt = 5
7、此時將整個陣列根據 piovt 分割成兩個部分，左邊都比 piovt 小，右邊都比 piovt 大。遞迴的處理左右兩部分。
實現
Java 版
public class QuickSort {
public static void main(String[] args) {
int[] nums = {5,1,4,6,2,66,34,8,34,534,5};
int[] sorted = sort(nums,0 , nums.length - 1);
System.out.println("finish!");
}
// 排序
public static int[] sort(int[] nums , int left , int right){
if(left <= right){
// 將 nums 以 mid 分成兩部分
// 左邊的小於 nums[min]
// 右邊的大於 nums[min]
int mid = partition(nums,left,right);
// 遞迴
sort(nums,left,mid - 1);
sort(nums,mid + 1 ,right);
}
return nums;
}
public static int partition(int[] nums , int left , int right){
//int pivot = left;
int i = left , j = right + 1; // 左右兩個指標
int pivot = nums[left]; // 基準數，比他小的放到左邊，比他大的放到右邊。
while ( true ){
// 從右向左找比 pivot 小的。
while (j > left && nums[--j] > pivot){
if(j == left){
// 到頭了
break;
}
}
// 先從左向右找比 pivot 大的。
while (i < right && nums[ ++ i] < pivot ){
if( i == right){
// 到頭了
break;
}
}
if(i >= j ) break;
// 交換 i 位置和 j 位置上的數
// 因為此時 nums[i] > pivot 並且 nums[j] < pivot
swap(nums,i , j);
}
// 由於 left 位置上的數是 pivot=
// 此時 i = j 且 nums[i/j] 左邊的數都小於 pivot , nums[i/j] 右邊的數都大於 pivot。
// 此時交換 left 和 j 位置上的數就是將 pivot 放到中間
swap(nums,left,j);
return j ;
}
// 交換陣列中兩個位置上的數
public static void swap(int[] nums , int i1 , int i2){
int n = nums[i1];
nums[i1] = nums[i2];
nums[i2] = n;
}
}
堆排序
堆排序主要是利用「堆」這種資料結構的特性來進行排序，它本質上類似於「選擇排序」。都是每次將最大值（或最小值），找出來放到數列尾部。不過「選擇排序」需要遍歷整個數列後選出最大值（可以到上面再熟悉下選擇排序演演算法），「堆排序」是依靠堆這種資料結構來選出最大值。但是每次重新構建最大堆用時要比遍歷整個數列要快得多。
堆排序中用到的兩種堆，大頂堆和小頂堆：
1、大頂堆：每個節點的值都大於或等於其子節點的值（在堆排序演演算法中一般用於升序排列）；
2、小頂堆：每個節點的值都小於或等於其子節點的值（在堆排序演演算法中一般用於降序排列）；
我們給樹的每個節點編號，並將編號對映到陣列的下標就是這樣：
該陣列從邏輯上是一個堆結構，我們用公式來描述一下堆的定義就是：
1、大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
2、小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
這裡只要求父節點大於兩個子節點，並沒有要求左右兩個子節點的大小關係。
演演算法過程
1、將一個 n 長的待排序序列arr = [0,……,n-1]構造成一個大頂堆。
2、此時陣列的 0 位置（也就是堆頂），就是陣列的最大值了，將其與陣列的最後一個數交換。
3、將剩下 n-1 個數重複 1和2 操作，最終會得到一個有序的序列。
堆排序是「選擇排序」的一種變體，演演算法中比較難的地方是用陣列構建「大頂堆」或「小頂堆」的過程。
實現堆排序前，我們要知道怎麼用陣列構建一個邏輯上的最大堆，這裡會用到幾個公式（假設當前節點的序號是 i，可以結合上圖理解下下面的公式）：
1、左子節點的序號就是：2i + 1；
2、右子幾點的序號就是：2i + 2；
3、父節點的序號就是：(i-1) / 2 （i不為0）；
實現
Java 版
public class HeapSort {
static int temp ;
public static void main(String[] args) {
int[] nums = {5,1,4,6,2,66,-1,34,-9,8};
sort(nums);
System.out.println("finish!");
}
public static void sort(int[] nums){
// 第一步要先將 nums 構建成最大堆。
for(int i = (nums.length - 1) / 2 ; i >= 0; i-- ){
//從第一個非葉子結點從下至上，從右至左調整結構
maxHeapify(nums,i,nums.length);
}
// 遍歷陣列
// j 是需要排序的陣列的最後一個索引位置。
for(int j = nums.length - 1 ; j > 0 ; j --){
// 每次都調整最大堆堆頂（nums[0]），與陣列尾的資料位置（nums[j]）。
swap(nums,0,j);
// 重新調整最大堆
maxHeapify(nums,0,j);
}
}
/**
* 將 nums 從 i 開始的 len 長度調整成最大堆。
* （注意：此方法只適合調整已經是最大堆但是被修改了的堆，或者只有三個節點的堆）
* len ：需要計算到陣列 nums 的多長的地方。
* i ：父節點在的位置。
*/
public static void maxHeapify(int[] nums,int i , int len){
// 是從左子節點開始
int key = 2 * i + 1;
if(key >= len){
// 說明沒有子節點。
return;
}
// key + 1 是右子節點的位置。
if(key + 1 < len && nums[key] < nums[key + 1]){
// 此時說明右節點比左節點大。
// 此時只要將父節點跟 右子節 點比就行了。
key += 1;
}
if(nums[i] < nums[key]){
// 子節點比父節點大，交換子父界節點的資料，將父節點設定為最大。
swap(nums,i,key);
// 此時子節點上的數變了，就要遞迴的再去，計運算元節點是不是最大堆。
maxHeapify(nums,key,len);
}
}
/**
* 交換 i 和 j 位置的資料
*/
public static void swap(int[] nums,int i,int j){
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
maxHeapify 這個方法有很多種實現，這裡用了個比較容易理解的遞迴實現。我看 dreamcatcher-cx 大佬寫了一種更好的實現方法，比較難理解一點，但是更高效，感興趣的見【參考4】。
參考
1、演演算法（第四版），by Robert Sedgewick/Kevin Wayne。
2、十大經典排序演演算法，by runnoob.com。
3、神級基礎排序——快速排序，by 江神。
4、圖解排序演演算法(三)之堆排序，by dreamcatcher-cx。