八大經典排序算法入門
- 2019 年 10 月 14 日
- 筆記
排序算法入門
在我們初學算法的時候，最先接觸到的就是排序算法，這些排序算法應用十分廣泛，而且是很多算法的基礎，可以說是每個程序員都必須得掌握的了。今天小編就來帶你一舉拿下經典的八大排序算法，每種算法都會有算法思想描述，動圖演示，代碼實現，複雜度及穩定性分析等。
01冒泡排序
1. 原理
假如我們要將一個無序數列升序排列，那麼冒泡排序的思想就是將“大”的元素經過交換慢慢“浮”到數列頂端，具體步驟如下：
a. 從第一個元素開始，比較該元素與它的下一個元素的大小，如果第一個大於第二個就交換兩個元素的位置，一直比較到序列末尾，我們稱這個為一輪排序過程，此時我們可以將數組分成未排序部分和有序部分（當前只有一個最大值）；
b. 對數組的未排序部分執行一輪冒泡排序，最大值加入有序部分（排在數組倒數第二位）；
c. 繼續對未排序數組執行上述操作，直到整個數組有序。
2. 演示
3. 代碼實現
1 public static int[] bubbleSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 for (int i = 0; i < array.length; i++){ 5 boolean isSwap = false; 6 for (int j = 0; j < array.length - 1 - i; j++) 7 if (array[j + 1] < array[j]) { 8 int temp = array[j + 1]; 9 array[j + 1] = array[j]; 10 array[j] = temp; 11 isSwap = true; 12 } 13 if(!isSwap) 14 break; 15 } 16 return array; 17 } 18
4. 時間複雜度
冒泡排序平均時間複雜度為O(n^2)，最好時間複雜度為O(n)，最壞時間複雜度為O(n^2)。
最好情況：如果待排序元素本來是正序的，那麼一趟冒泡排序就可以完成排序工作，比較和移動元素的次數分別是 (n – 1) 和 0，因此最好情況的時間複雜度為O(n)。
最壞情況：如果待排序元素本來是逆序的，需要進行 (n – 1) 趟排序，所需比較和移動次數分別為 n * (n – 1) / 2和 3 * n * (n-1) / 2。因此最壞情況下的時間複雜度為O(n^2)。
5. 空間複雜度
冒泡排序使用了常數空間，空間複雜度為O(1)
6. 穩定性
當 array[j] == array[j+1] 的時候，我們不交換 array[i] 和 array[j]，所以冒泡排序是穩定的。
02選擇排序
1. 原理
選擇排序是從未排序序列中找到最小（大）元素，放到排序序列起始位置，然後從剩餘未排序序列中繼續找最小（大）元素，放到已排序序列的末尾，具體步驟如下：
a. 初始時，整個數組為無序數組A[0…n-1]，有序數組為空；
b. 第i趟排序（i=0,1,…,n-2），從A[i+1…n-1]中找到最小的元素，將它與第i個元素交換；
c. i=n-1時，排序結束。
2. 演示
3. 代碼實現
1 public static int[] selectionSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 for (int i = 0; i < array.length; i++) { 5 int minIndex = i; 6 for (int j = i; j < array.length; j++) { 7 if (array[j] < array[minIndex]) 8 minIndex = j; 9 } 10 int temp = array[minIndex]; 11 array[minIndex] = array[i]; 12 array[i] = temp; 13 } 14 return array; 15 }
4. 時間複雜度
簡單選擇排序平均時間複雜度為O(n^2)，最好時間複雜度為O(n^2)，最壞時間複雜度為O(n^2)。
最好情況：如果待排序元素本來是正序的，則移動元素次數為 0，但需要進行 n * (n – 1) / 2 次比較。
最壞情況：如果待排序元素中第一個元素最大，其餘元素從小到大排列，則仍然需要進行 n * (n – 1) / 2 次比較，且每趟排序都需要移動 3 次元素，即移動元素的次數為3 * (n – 1)次。
需要注意的是，簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序元素的排列情況無關。
5. 空間複雜度
簡單選擇排序使用了常數空間，空間複雜度為O(1)
6. 穩定性
簡單選擇排序不穩定，比如序列 2、4、2、1，我們知道第一趟排序第 1 個元素 2 會和 1 交換，那麼原序列中 2 個 2 的相對前後順序就被破壞了，所以簡單選擇排序不是一個穩定的排序算法。
03插入排序
1. 原理
對未排序的序列，在已排序的序列中從後向前掃描，找到相應的位置插入，具體步驟如下：
a. 從第一個元素開始，認為該元素已經被排序；
b. 取出未排序數組的第一個元素a，在已經排序的元素序列中從後先前掃描，如果該元素大於a，將該元素移到下一個位置；
c.繼續向前找直到找到一個元素小於或等於a，則將a插入該元素後面；
d. 重複步驟b,c，直到未排序序列為空。
2. 演示
3. 代碼實現
1 public static int[] insertionSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 int current; 5 for (int i = 1; i < array.length; i++) { 6 current = array[i]; 7 int preIndex = i - 1; 8 while (preIndex >= 0 && current < array[preIndex]) { 9 array[preIndex + 1] = array[preIndex]; 10 preIndex--; 11 } 12 array[preIndex + 1] = current; 13 } 14 return array; 15 }
4. 時間複雜度
直接插入排序平均時間複雜度為O(n^2)，最好時間複雜度為O(n)，最壞時間複雜度為O(n^2)。
最好情況：如果待排序元素本來是正序的，則移動元素次數為 0，但需要進行(n – 1)次比較。
最壞情況：如果待排序元素本來就是逆序，需要進行(n-1)趟排序，比較和移動的次數分別是n*(n-1)/2 和 n*(n-1)/2，所以最壞情況下時間複雜度為O(n^2)。
5. 空間複雜度
直接插入排序使用了常數空間，空間複雜度為O(1)
6. 穩定性
直接插入排序是穩定的。
04希爾排序
1. 原理
希爾排序是第一個突破O(n^2)的排序算法，是直接插入排序的改進算法，是一種縮小增量排序，具體步驟如下：
a. 將整個序列分割成gap個子序列（gap初始值一般取len/2），每個子序列由位置相差為gap的元素組成，每個子系列有n/gap個元素；
b. 對每一個子序列分別進行直接插入排序，然後縮減gap為原來的一般在進行插排；
c.當gap==1時，希爾排序變成直接插入排序，而此時序列已經基本有序，效率很高；
2. 演示
3. 代碼實現
1 public static int[] ShellSort(int[] array) { 2 int len = array.length; 3 if(len == 0) 4 return array; 5 int current, gap = len / 2; 6 while (gap > 0) { 7 for (int i = gap; i < len; i++) { 8 current = array[i]; 9 int preIndex = i - gap; 10 while (preIndex >= 0 && array[preIndex] > current) { 11 array[preIndex + gap] = array[preIndex]; 12 preIndex -= gap; 13 } 14 array[preIndex + gap] = current; 15 } 16 gap /= 2; 17 } 18 return array; 19 }
4. 時間複雜度
希爾排序平均時間複雜度為O(nlogn)，最好時間複雜度為O(nlogn)，最壞時間複雜度為O(nlogn)。其時間複雜度與增量序列的選取有關。
5. 空間複雜度
希爾排序使用了常數空間，空間複雜度為O(1)
6. 穩定性
相同元素可能在不同的子序列中進行插入排序，穩定性會被打亂。
05歸併排序
1. 原理
歸併排序是採用分治法的排序算法，主要思想是將已有序的子序列合併成更長的有序序列，具體步驟如下：
a. 將長度為n的序列分成兩個長度為n/2的子序列；
b. 對這兩個子序列分別採用歸併排序；
c.將兩個排好序的子序列合併成一個排序序列；
2. 演示
3. 代碼實現
1 public static int[] MergeSort(int[] array) { 2 if (array.length < 2) return array; 3 int mid = array.length / 2; 4 int[] left = Arrays.copyOfRange(array, 0, mid); 5 int[] right = Arrays.copyOfRange(array, mid, array.length); 6 return merge(MergeSort(left), MergeSort(right)); 7 } 8 public static int[] merge(int[] left, int[] right) { 9 int[] result = new int[left.length + right.length]; 10 int i = 0,j = 0,k = 0; 11 while (i < left.length && j < right.length) { 12 if (left[i] <= right[j]) { 13 result[k++] = left[i++]; 14 } else { 15 result[k++] = right[j++]; 16 } 17 } 18 while (i < left.length) { 19 result[k++] = left[i++]; 20 } 21 while (j < right.length) { 22 result[k++] = right[j++]; 23 } 24 return result; 25 }
4. 時間複雜度
歸併排序平均時間複雜度為O(nlogn)，最好時間複雜度為O(nlogn)，最壞時間複雜度為O(nlogn)。
5. 空間複雜度
空間複雜度為O(n)
6. 穩定性
歸併排序是穩定的。
06快速排序
1. 原理
快速排序就是給基準數找到其正確的索引位置的過程，它其實是基於分治的思想，具體步驟如下：
a. 在數組中選擇一個基準點（基準點的選取可能影響效率）；
b. 分別從數組兩端掃描，left指向起始位置，right指向末尾，先從後向前掃，如果發現有元素比該基準值小，就交換left和right對應元素的值，然後從前往後掃，如果發現有元素比該基準值大，就交換left和right對應元素值，如此往複，直到left>=right，然後把基準值放到left索引的位置；
c.以基準值最終索引的位置為分割點，分別遞歸地對前後兩部分進行排序；
2. 演示
3. 代碼實現
1 public static void Quicksort(int array[], int left, int right) { 2 if(left < right){ 3 int pos = partition(array, left, right); 4 Quicksort(array, left, pos - 1); 5 Quicksort(array, pos + 1, right); 6 } 7 } 8 public static int partition(int[] array,int left,int right) { 9 int key = array[left]; 10 while(left < right) { 11 while(left < right && array[left] <= key ) 12 left++; 13 array[right] = array[left]; 14 while(left <right && array[right] >= key) 15 right--; 16 array[left] = array[right]; 17 } 18 array[left] = key; 19 return left; 20 }
4. 時間複雜度
快速排序平均時間複雜度為O(nlogn)，最好時間複雜度為O(nlogn)，最壞時間複雜度為O(n^2)。
5. 空間複雜度
主要考慮遞歸時使用的棧空間，最好情況下partition每次恰好能均分序列，空間複雜度為O(logn),最壞情況下，退化為冒泡排序，空間複雜度為O(n)，平均為O(logn).
6. 穩定性
快速排序是不穩定的。
07堆排序
1. 原理
堆排序是基於堆這種數據結構的排序算法，將數組看作一棵完全二叉樹的存儲結構，利用完全二叉樹中父節點和孩子結點之間的關係選取最大（小）元素，具體步驟如下：
a. 將數組構建成大頂堆，此時最大元素是堆頂元素；
b. 將堆頂元素與最後一個元素交換，然後對堆中除最後一個元素以外的元素重新調整為一個大根堆；
c.重複b，堆中只有一個元素；
2. 演示
3. 代碼實現
1 public static int[] HeapSort(int[] array) { 2 len = array.length; 3 if (len == 0) return array; 4 buildMaxHeap(array); 5 while (len > 0) { 6 swap(array, 0, len - 1); 7 len--; 8 adjustHeap(array, 0); 9 } 10 return array; 11 } 12 public static void adjustHeap(int[] array, int i) { 13 int maxIndex = i; 14 if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex]) 15 maxIndex = 2 * i + 1; 16 if (2 * i + 2 < len && array[2 * i + 2] > array[maxIndex]) 17 maxIndex = 2 * i + 2; 18 if (maxIndex != i) { 19 swap(array, maxIndex, i); 20 adjustHeap(array, maxIndex); 21 } 22 } 23 public static void buildMaxHeap(int[] array) { 24 for (int i = (len - 2) / 2; i >= 0; i--) { 25 adjustHeap(array, i); 26 } 27 }
4. 時間複雜度
堆排序平均時間複雜度為O(nlogn)，最好時間複雜度為O(nlogn)，最壞時間複雜度為O(nlogn)。
5. 空間複雜度
堆排序使用常數空間O(1).
6. 穩定性
堆排序是不穩定的。
08計數排序
1. 原理
計數排序不是基於比較的排序算法，它要求輸入數據必須是有確定範圍的整數，主要原理是將輸入數據轉化為鍵存儲在額外開闢的數組空間中，是一種線性時間複雜度的排序，具體步驟如下：
a. 找出數組中的最大和最小元素；
b. 統計數組中每個值為i的元素出現的次數，存入計數數組C的第i項；
c.對所有計數進行累加，從計數數組的第一個元素開始，每一項和前一項相加；
d. 反向填充數組，每個元素i放在新數組的C[i]位置，每放一個元素就將C[i]減去1.
2. 演示
3. 代碼實現
1 public static int[] CountingSort(int[] array) { 2 if (array.length == 0) return array; 3 int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; 4 for (int i = 0; i < array.length; i++) { 5 max = Math.max(max, array[i]); 6 min = Math.min(min, array[i]); 7 } 8 bias = -min; 9 int[] bucket = new int[max - min + 1]; 10 Arrays.fill(bucket, 0); 11 for (int i = 0; i < array.length; i++) { 12 bucket[array[i] + bias]++; 13 } 14 int index = 0, i = 0; 15 while (index < array.length) { 16 if (bucket[i] != 0) { 17 array[index] = i - bias; 18 bucket[i]--; 19 index++; 20 } else 21 i++; 22 } 23 return array; 24 }
4. 時間複雜度
計數排序時間複雜度為O(n+k)，n為遍歷一趟數組計數過程的複雜度，k為遍歷一趟桶取出元素過程的時間複雜度。
5. 空間複雜度
計數排序使用空間O(k)，k為桶數組的長度。
6. 穩定性
堆排序是穩定的。
關注我 獲取更多知識
長按掃碼關注
