## 排序 [TOC] ### 1\. 選擇排序（Selection Sort） 選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的主要思路是每次從未排序的部分中選出最小（或最大）的元素，放到已排序部分的末尾，直到所有元素都被排序為止。 ### 選擇排序的邏輯 1. **初始狀態：** 將數組分為已排序部分和未排序部分。開始時，已排序部分為空，未排序部分包含整個數組。 2. **選擇最小值：** 在未排序部分中找到最小值。 3. **交換位置：** 將這個最小值與未排序部分的第一個元素交換位置，使其進入已排序部分。 4. **重復步驟：** 對未排序部分重復上述步驟，直到未排序部分為空。 ### 時間復雜度 選擇排序的時間復雜度為 O(n2)，其中 n是數組的長度。它在每次選擇最小值時需要掃描未排序部分，導致時間復雜度較高。 ### 代碼示例 ~~~ public class SelectionSort { // 主函數：用于演示選擇排序的實現 public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; // 定義待排序的數組 selectionSort(arr); // 調用選擇排序算法 printArray(arr); // 打印排序后的數組 } // 選擇排序算法的實現 public static void selectionSort(int[] arr) { int n = arr.length; // 獲取數組長度 // 遍歷數組，依次找到最小元素并放到已排序部分的末尾 for (int i = 0; i < n - 1; i++) { int minIndex = i; // 假設當前未排序部分的第一個元素是最小值 for (int j = i + 1; j < n; j++) { // 遍歷未排序部分 if (arr[j] < arr[minIndex]) { // 如果找到比假設最小值更小的元素 minIndex = j; // 更新最小值的索引 } } // 交換最小值和未排序部分第一個元素的位置 int temp = arr[minIndex]; // 臨時變量保存最小值 arr[minIndex] = arr[i]; // 將未排序部分第一個元素放到最小值的位置 arr[i] = temp; // 將最小值放到已排序部分的末尾 } } // 輔助函數：打印數組內容 public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { // 遍歷數組的每個元素 System.out.print(arr[i] + " "); // 打印元素 } System.out.println(); // 換行，便于下一次輸出 } } ~~~ ### 代碼說明 * **selectionSort方法：** 該方法實現了選擇排序算法。首先，外層循環從頭到尾遍歷數組，每次選擇出一個最小值放到已排序部分的末尾。內層循環在未排序部分找到最小值，并記錄其位置，最后通過交換將最小值放置到正確的位置。 * **printArray方法：** 用于打印數組內容。排序后調用這個方法可以看到排序結果。 選擇排序的優點是算法簡單易懂，代碼量少，適用于數據量較小的場景。缺點是時間復雜度較高，不適合處理大量數據。 ### 2\. 插入排序（Insertion Sort） 插入排序從左到右進行，每次都將當前元素插入到左側已經排序的數組中，使得插入之后左部數組依然有序。 第 j 元素是通過不斷向左比較并交換來實現插入過程：當第 j 元素小于第 j - 1 元素，就將它們的位置交換，然后令 j 指針向左移動一個位置，不斷進行以上操作。 [](https://camo.githubusercontent.com/5e6dcf3d502a864805ecd49fefac164dd91e4b49/68747470733a2f2f696d61676573323031372e636e626c6f67732e636f6d2f626c6f672f3834393538392f3230313731302f3834393538392d32303137313031353232353634353237372d313135313130303030302e676966) **代碼實現** ~~~java public static void sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j > 0; j--) { if (arr[j] < arr[j - 1]) swap(arr, j, j - 1); // 大量的交換會消耗時間 else break; } } } // 改進版插入排序（減少了數組元素的操作次數） public static void better_sort(int[] arr) { for (int i = 0; i < arr.length; i++) { int e = arr[i]; int j = i; for (; j > 0; j--) { if (e < arr[j - 1]) arr[j] = arr[j - 1]; else break; } arr[j] = e; } } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } ~~~ **算法分析** 插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。 ### 3\. 冒泡排序（Bubble Sort） 通過從左到右不斷交換相鄰逆序的相鄰元素，在一輪的交換之后，可以讓未排序的元素上浮到右側。 在一輪循環中，如果沒有發生交換，就說明數組已經是有序的，此時可以直接退出。 [](https://camo.githubusercontent.com/adaf3658c694ce232520c3f2b677b3273e0e6c1a/68747470733a2f2f696d61676573323031372e636e626c6f67732e636f6d2f626c6f672f3834393538392f3230313731302f3834393538392d32303137313031353232333233383434392d323134363136393139372e676966) **代碼實現** ~~~java private static void sort(int[] arr) { for (int i = arr.length - 1; i > 0; i--) { // 從最后一位開始確定 boolean swapped = false; for (int j = 0; j < i; j++) { if(arr[j] > arr[j+1]){ swapped = true; swap(arr,j,j+1); } } if(!swapped) return; } } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } ~~~ ### 4\. 希爾排序（Shell Sort） 1959年Shell發明，第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫**縮小增量排序**。 **算法描述** 先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述： * 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1； * 按增量序列個數k，對序列進行k 趟排序； * 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。 [](https://camo.githubusercontent.com/fda52e27af7d3624e110e94109c28fd27fa44871/68747470733a2f2f696d61676573323031382e636e626c6f67732e636f6d2f626c6f672f3834393538392f3230313830332f3834393538392d32303138303333313137303031373432312d3336343530363037332e676966) **代碼實現** ~~~java // 希爾排序 public static void sort(int[] arr) { int n = arr.length; for (int h = n / 2; h > 0; h = h / 2) { // 內部是一個插入排序 for (int i = 0; i < n; i = i + h) { int e = arr[i]; int j = i; for (; j > 0; j = j - h) { if (e < arr[j - h]) arr[j] = arr[j - h]; else break; } arr[j] = e; } } } // 希爾排序2 public static void sort2(int[] arr) { int n = arr.length; // 計算 increment sequence: 1, 4, 13, 40, 121, 364, 1093... int h = 1; while (h < n / 3) h = 3 * h + 1; System.out.println(h); while (h >= 1) { // h-sort the array for (int i = h; i < n; i++) { // 對 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序 int e = arr[i]; int j = i; for (; j >= h && e < arr[j - h]; j -= h) arr[j] = arr[j - h]; arr[j] = e; } h /= 3; } } ~~~ **算法分析** 對于大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。 希爾排序的出現就是為了改進插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大于 1。 希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最后令 h=1，就可以使得整個數組是有序的。 ### 5\. 歸并排序（Merge Sort） 歸并排序的思想是將數組分成兩部分，分別進行排序，然后歸并起來。把長度為n的輸入序列分成兩個長度為n/2的子序列；對這兩個子序列分別采用歸并排序；將兩個排序好的子序列合并成一個最終的排序序列。 [](https://camo.githubusercontent.com/207472a2903254f1706938a09fc3fa854ad23273/68747470733a2f2f696d61676573323031372e636e626c6f67732e636f6d2f626c6f672f3834393538392f3230313731302f3834393538392d32303137313031353233303535373034332d33373337353031302e676966) **代碼實現** > 1.歸并方法 > > 歸并方法將數組中兩個已經排序的部分歸并成一個。 ~~~java private static void sort(int[] arr) { __MergeSort(arr, 0, arr.length - 1); } private static 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); } // 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并 private static void merge(int[] arr, int l, int mid, int r) { int[] aux = Arrays.copyOfRange(arr, l, r + 1); // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { // 如果左半部分元素已經全部處理完畢 arr[k] = aux[j - l]; j++; } else if (j > r) { // 如果右半部分元素已經全部處理完畢 arr[k] = aux[i - l]; i++; } else if (aux[i - l] < aux[j - l]) { // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i - l]; i++; } else { // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j - l]; j++; } } } ~~~ > 2.自底向上歸并排序 ~~~java private static void sort(int[] arr) { int N = arr.length; int[] aux = new int[N]; for (int sz = 1; sz < N; sz += sz) for (int i = 0; i + sz < N; i += sz + sz) merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, N - 1)); } ~~~ ### 6\. 快速排序（Quick Sort） 快速排序可以說是20世紀最偉大的算法之一了。相信都有所耳聞，它的速度也正如它的名字那樣，是一個非常快的算法了。當然它也后期經過了不斷的改進和優化，才被公認為是一個值得信任的非常優秀的算法。 [](https://camo.githubusercontent.com/4a10c066718dc2584d2b1682f8b2085920db0123/68747470733a2f2f696d61676573323031372e636e626c6f67732e636f6d2f626c6f672f3834393538392f3230313731302f3834393538392d32303137313031353233303933363337312d313431333532333431322e676966) **代碼實現** #### 1\. 普通快速排序 ~~~java // 遞歸使用快速排序,對arr[l...r]的范圍進行排序 public static void QuickSort(int[] arr,int l,int r){ if(l>=r) return; int p = partition(arr,l,r); QuickSort(arr,l,p-1); QuickSort(arr,p+1,r); } // 將數組通過p分割成兩部分 // 對arr[l...r]部分進行partition操作 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] public static int partition(int[] arr, int l, int r) { swap(arr, l, (int) (Math.random() % (r - l + 1)) + l); // 加入這一行變成隨機快速排序 int v = arr[l]; int j = l; for(int i = j +1;i<=r;i++){ if(arr[i] < v){ j++; swap(arr,i,j); } } swap(arr,l,j); return j; } public static void swap(int[] arr,int i,int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } ~~~ 快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。 快速排序最好的情況下是每次都正好能將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，復雜度為 O(NlogN)。 最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。 #### 2\. 雙路快速排序 若果數組中含有大量重復的元素，則partition很可能把數組劃分成兩個及其不平衡的兩部分，時間復雜度退化成O(n2)。這時候應該把小于v和大于v放在數組兩端。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/partition2.jpg) ~~~java // 雙路快速排序的partition // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] private static int partition(int[] arr, int l, int r) { // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot // swap(arr, l, (int) (Math.random() % (r - l + 1)) + l); int v = arr[l]; // arr[l+1...i) <= v; arr(j...r] >= v int i = l + 1, j = r; while (true) { // 注意這里的邊界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0 // 思考一下為什么? while (i <= r && arr[i] < v) i++; // 注意這里的邊界, arr[j].compareTo(v) > 0, 不能是arr[j].compareTo(v) >= 0 // 思考一下為什么? while (j >= l + 1 && arr[j] > v) j--; // 對于上面的兩個邊界的設定, 有的同學在課程的問答區有很好的回答:) // 大家可以參考: http://coding.imooc.com/learn/questiondetail/4920.html if (i > j) break; swap(arr, i, j); i++; j--; } swap(arr, l, j); return j; } // 遞歸使用快速排序,對arr[l...r]的范圍進行排序 private static void QuickSort2Ways(int[] arr, int l, int r) { // 對于小規模數組, 使用插入排序 if (l >= r) return; int p = partition(arr, l, r); QuickSort2Ways(arr, l, p - 1); QuickSort2Ways(arr, p + 1, r); } ~~~ #### 3\. 三路快速排序 數組分成三個部分，大于v 等于v 小于v 在具有大量重復鍵值對的情況下使用三路快排 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/partition3.jpg) ~~~java // 遞歸使用快速排序,對arr[l...r]的范圍進行排序 private static void QuickSort3Ways(int[] arr, int l, int r){ // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot swap( arr, l, (int)(Math.random()*(r-l+1)) + l ); int v = arr[l]; int lt = l; // arr[l+1...lt] < v int gt = r + 1; // arr[gt...r] > v int i = l+1; // arr[lt+1...i) == v while( i < gt ){ if( arr[i] < v){ swap( arr, i, lt+1); i ++; lt ++; } else if( arr[i] > v ){ swap( arr, i, gt-1); gt --; } else{ // arr[i] == v i ++; } } swap( arr, l, lt ); QuickSort3Ways(arr, l, lt-1); QuickSort3Ways(arr, gt, r); } ~~~ ### 7\. 堆排序（Heap Sort） #### 1\. 堆 堆的某個節點的值總是大于等于子節點的值，并且堆是一顆完全二叉樹。 堆可以用數組來表示，因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這里不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關系。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/heap.png) #### 2\. 上浮和下沉 在堆中，當一個節點比父節點大，那么需要交換這個兩個節點。交換后還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為**上浮（ShiftUp）**。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/shiftup_heap.png) ~~~java private void shiftUp(int k){ while( k > 1 && data[k/2] < data[k])){ swap(k, k/2); k /= 2; } } ~~~ 類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為**下沉（Shift Down）**。一個節點如果有兩個子節點，應當與兩個子節點中最大那么節點進行交換。 [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/shiftdown_heap.png) ~~~java private void shiftDown(int k){ while( 2*k <= count ){ // 當前結點有左孩子 int j = 2*k; // 在此輪循環中,data[k]和data[j]交換位置 if( j+1 <= count && data[j+1] > data[j] ) j ++; // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if( data[k] >= data[j] ) break; swap(k, j); k = j; } } ~~~ #### 3.插入元素 將新元素放到數組末尾，然后上浮到合適的位置。 ~~~java // 向最大堆中插入一個新的元素 item public void insert(Item item){ assert count + 1 <= capacity; data[count+1] = item; count ++; shiftUp(count); } ~~~ #### 4\. 刪除最大元素 ~~~java // 從最大堆中取出堆頂元素, 即堆中所存儲的最大數據 public Item extractMax(){ assert count > 0; Item ret = data[1]; swap( 1 , count ); count --; shiftDown(1); return ret; } ~~~ #### 5\. 堆排序 由于堆可以很容易得到最大的元素并刪除它，不斷地進行這種操作可以得到一個遞減序列。如果把最大元素和當前堆中數組的最后一個元素交換位置，并且不刪除它，那么就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列。因此很容易使用堆來進行排序。并且堆排序是原地排序，不占用額外空間。 ~~~java // 不使用一個額外的最大堆, 直接在原數組上進行原地的堆排序 public class HeapSort { // 對整個arr數組使用HeapSort1排序 // HeapSort1, 將所有的元素依次添加到堆中, 在將所有元素從堆中依次取出來, 即完成了排序 // 無論是創建堆的過程, 還是從堆中依次取出元素的過程, 時間復雜度均為O(nlogn) // 整個堆排序的整體時間復雜度為O(nlogn) public static void sort1(Comparable[] arr){ int n = arr.length; MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(n); for( int i = 0 ; i < n ; i ++ ) maxHeap.insert(arr[i]); for( int i = n-1 ; i >= 0 ; i -- ) arr[i] = maxHeap.extractMax(); } // 只通過shiftDown操作進行排序 public static void sort2(Comparable[] arr){ int n = arr.length; // 注意，此時我們的堆是從0開始索引的 // 從(最后一個元素的索引-1)/2開始 // 最后一個元素的索引 = n-1 for( int i = (n-1-1)/2 ; i >= 0 ; i -- ) shiftDown2(arr, n, i); for( int i = n-1; i > 0 ; i-- ){ // 這個的目的是讓序列從小到大排序 swap( arr, 0, i); shiftDown2(arr, i, 0); } } // 交換堆中索引為i和j的兩個元素 private static void swap(Object[] arr, int i, int j){ Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // 原始的shiftDown過程 private static void shiftDown(Comparable[] arr, int n, int k){ while( 2*k+1 < n ){ int j = 2*k+1; if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 ) j += 1; if( arr[k].compareTo(arr[j]) >= 0 )break; swap( arr, k, j); k = j; } } // 優化的shiftDown過程, 使用賦值的方式取代不斷的swap, // 該優化思想和我們之前對插入排序進行優化的思路是一致的 private static void shiftDown2(Comparable[] arr, int n, int k){ Comparable e = arr[k]; while( 2*k+1 < n ){ int j = 2*k+1; if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 ) j += 1; if( e.compareTo(arr[j]) >= 0 ) break; arr[k] = arr[j]; k = j; } arr[k] = e; } // 測試 HeapSort public static void main(String[] args) { Integer[] arr = {10, 91, 8, 7, 6, 5, 4, 3, 2, 1}; HeapSort.sort2(arr); PrintHelper.printArray(arr); } } ~~~ #### 6\. 堆排序的應用——Top K問題 例如，有1億個浮點數，如何找出其中最大的10000個？（B326） ###8\. 計數排序 [https://www.cnblogs.com/freedom314/p/5847092.html](https://www.cnblogs.com/freedom314/p/5847092.html) ### 9\. 排序算法總結 | | 平均時間復雜度 | 原地排序 | 額外空間 | 穩定排序 | | :-: | :-: | :-: | :-: | :-: | | 插入排序 | O(n^2) | √ | O(1) | √ | | 歸并排序 | O(nlogn) | × | O(n) | √ | | 快速排序 | O(nlogn) | √ | O(logn) | × | | 堆排序 | O(nlogn) | √ | O(1) | × | 穩定排序：對于相等的元素，在排序后，原來靠前的元素依然靠前。相等元素的相對位置沒有發生變化。 ~~~java // 可以通過?自定義?比較函數，讓排序算法不不存在穩定性的問題。 bool operator<(const Student& otherStudent){ return score != otherStudent.score ? score > otherStudent.score : name < otherStudent.name; } ~~~ [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/pics/sort_algorithm_analyze.png)