# 常見排序算法 參考極客時間《數據結構與算法之美》專欄整理 ## 常見排序算法對比 | 排序算法 | 時間復雜度 | 是否基于比較 | | ---------------- | ---------- | :----------- | | 冒泡、插入、選擇 | O(n^2) | 是 | | 快排、歸并 | O(nlogn) | 是 | | 桶、技術、基數 | O(n) | 否 | ## 排序算法的分析 ### 排序算法的執行效率 * 最好情況、最壞情況、平均時間復雜度 * 時間復雜度的系數、常數、低階 在數據量n很大的時候我們會忽略系數、常數、低階，但如果針對數據量情況較小（10、100、1000這種量級），就需要把系數、常數、低階考慮進來 * 比較次數和交換（或移動）次數 基于比較的排序算法的執行過程中，會涉及到元素的交換或移動。所以分析排序算法的執行效率的時候，也應該把比較次數和交換（或移動）次數考慮進去 ### 排序算法的內存消耗 針對排序算法的空間復雜度，引入一個新的概念，**原地排序**（Sorted in place）。原地排序算法，就是特指空間復雜度是O(1)的排序算法。 ### 排序算法的穩定性 **穩定性**指的是如果待排序中存在值相等的元素，經過排序后，相等元素之間原有的順序不變。例如，一批訂單數據，先按時間從最近往前開始進行排序，然后再按照金額從高到低排序。在保證排序算法穩定性的情況下最后結果金額能從高到低的同時下，相同金額的訂單能從最近開始往后排，顯然這樣的排序結果更具有意義。 ## 冒泡排序算法 `// 冒泡排序，a 表示數組，n 表示數組大小 public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循環的標志位 boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交換 int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true; // 表示有數據交換 } } if (!flag) break; // 沒有數據交換，提前退出 } }` ## 插入排序算法 `// 插入排序，a 表示數組，n 表示數組大小 public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置 for (; j >= 0; --j) { if (a[j] > value) { a[j+1] = a[j]; // 數據移動 } else { break; } } a[j+1] = value; // 插入數據 } }` ## 選擇排序算法