好的，下面為你整理一篇面試全覆蓋、極其深入的十大排序算法總結博客，涵蓋算法原理、復雜度、穩定性、應用場景、工程實踐、C++與Python實現（含詳細注釋），并對比分析各種排序的優缺點與適用情境。內容力求結構清晰、講解透徹，適合面試復習與深入學習。
十大排序算法全解析（面試高頻+工程實用）
一、排序算法總覽
| 排序算法 | 平均時間復雜度 | 最好 | 最壞 | 空間復雜度 | 穩定性 | 適用場景/特點 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 穩定 | 小規模/基本有序 |
| 選擇排序 | O(n2) | O(n2) | O(n2) | O(1) | 不穩定 | 小規模/交換少 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 穩定 | 小規模/基本有序 |
| 希爾排序 | O(n^1.3~2) | O(n) | O(n2) | O(1) | 不穩定 | 中等規模/優化插入 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩定 | 大規模/鏈表/外部排序 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | 不穩定 | 大規模/工程常用 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩定 | 大規模/原地排序 |
| 計數排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 穩定 | 整數/范圍小 |
| 基數排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 穩定 | 整數/字符串/大數據 |
| 桶排序 | O(n)~O(n2) | O(n) | O(n2) | O(n+k) | 穩定 | 均勻分布/浮點數 |
穩定性：相等元素排序后相對順序是否保持不變。
空間復雜度：是否原地排序，是否需要輔助數組。
適用場景：數據規模、分布、是否有負數、是否鏈表等。
二、三種元素交換方法（C++/Python）
1. 臨時變量法（推薦，安全）
void swap(int &a, int &b) {int tmp = a;a = b;b = tmp;
}
def swap(arr, i, j):arr[i], arr[j] = arr[j], arr[i]
2. 加減法（需防溢出，i!=j）
void swap(int &a, int &b) {if (&a == &b) return;a = a + b;b = a - b;a = a - b;
}
3. 異或法（僅限整數，i!=j）
void swap(int &a, int &b) {if (&a == &b) return;a ^= b;b ^= a;a ^= b;
}
三、十大排序算法詳解
1. 冒泡排序（Bubble Sort）
原理
- 每輪將最大（或最小）元素“冒泡”到末尾。
- 優化：若一輪無交換，提前結束。
復雜度
- 時間：O(n2)，最好O(n)（已排序）
- 空間：O(1)
- 穩定性：穩定
C++實現
void bubbleSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {bool swapped = false;for (int j = 1; j < n - i; ++j) {if (arr[j-1] > arr[j]) {swap(arr[j-1], arr[j]);swapped = true;}}if (!swapped) break; // 已有序，提前結束}
}
Python實現
def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(1, n-i):if arr[j-1] > arr[j]:arr[j-1], arr[j] = arr[j], arr[j-1]swapped = Trueif not swapped:break
應用場景
- 小規模、基本有序數組
- 代碼簡單，教學常用
2. 選擇排序（Selection Sort）
原理
- 每輪選擇最小（或最大）元素放到前面。
復雜度
- 時間：O(n2)
- 空間：O(1)
- 穩定性：不穩定（跨越交換）
C++實現
void selectionSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n-1; ++i) {int minIdx = i;for (int j = i+1; j < n; ++j)if (arr[j] < arr[minIdx]) minIdx = j;if (minIdx != i) swap(arr[i], arr[minIdx]);}
}
Python實現
def selection_sort(arr):n = len(arr)for i in range(n-1):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jif min_idx != i:arr[i], arr[min_idx] = arr[min_idx], arr[i]
應用場景
- 小規模、交換次數少
- 不要求穩定性
3. 插入排序（Insertion Sort）
原理
- 每次將一個元素插入到已排序部分的合適位置。
復雜度
- 時間：O(n2)，最好O(n)
- 空間：O(1)
- 穩定性：穩定
C++實現
void insertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i], j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];--j;}arr[j+1] = key;}
}
Python實現
def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and arr[j] > key:arr[j+1] = arr[j]j -= 1arr[j+1] = key
應用場景
- 小規模、基本有序
- 鏈表排序
4. 希爾排序（Shell Sort）
原理
- 分組插入排序，逐步縮小gap，最終gap=1變插入排序。
- 增量序列影響復雜度（Shell/Hibbard/Knuth/Sedgewick等）。
復雜度
- 時間：O(n^1.3~2)，依賴gap序列
- 空間：O(1)
- 穩定性：不穩定
C++實現（Shell增量）
void shellSort(vector<int>& arr) {int n = arr.size();for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = arr[i], j = i;while (j >= gap && arr[j-gap] > temp) {arr[j] = arr[j-gap];j -= gap;}arr[j] = temp;}}
}
Python實現
def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] > temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap //= 2
應用場景
- 中等規模
- 插入排序的優化
5. 歸并排序（Merge Sort）
原理
- 分治法，遞歸分成兩半，合并時排序。
復雜度
- 時間：O(nlogn)
- 空間：O(n)（非原地）
- 穩定性：穩定
C++實現
void merge(vector<int>& arr, int l, int m, int r) {vector<int> left(arr.begin()+l, arr.begin()+m+1);vector<int> right(arr.begin()+m+1, arr.begin()+r+1);int i = 0, j = 0, k = l;while (i < left.size() && j < right.size())arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];while (i < left.size()) arr[k++] = left[i++];while (j < right.size()) arr[k++] = right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {if (l >= r) return;int m = l + (r-l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);
}
Python實現
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr)//2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])res = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:res.append(left[i])i += 1else:res.append(right[j])j += 1res.extend(left[i:])res.extend(right[j:])return res
應用場景
- 大規模、鏈表排序
- 外部排序（磁盤/大數據）
6. 快速排序（Quick Sort）
原理
- 分治法，選主元分區，遞歸排序兩側。
- 主元選取方式影響性能（首位/隨機/三數取中）。
復雜度
- 時間：O(nlogn)，最壞O(n2)
- 空間：O(logn)（遞歸棧）
- 穩定性：不穩定
C++實現（隨機主元）
int partition(vector<int>& arr, int l, int r) {int pivot = arr[l];int i = l+1, j = r;while (true) {while (i <= j && arr[i] < pivot) ++i;while (i <= j && arr[j] > pivot) --j;if (i >= j) break;swap(arr[i++], arr[j--]);}swap(arr[l], arr[j]);return j;
}
void quickSort(vector<int>& arr, int l, int r) {if (l >= r) return;int mid = l + rand() % (r-l+1);swap(arr[l], arr[mid]);int p = partition(arr, l, r);quickSort(arr, l, p-1);quickSort(arr, p+1, r);
}
Python實現
import random
def quick_sort(arr, l, r):if l >= r:returnpivot_idx = random.randint(l, r)arr[l], arr[pivot_idx] = arr[pivot_idx], arr[l]pivot = arr[l]i, j = l+1, rwhile True:while i <= j and arr[i] < pivot:i += 1while i <= j and arr[j] > pivot:j -= 1if i >= j:breakarr[i], arr[j] = arr[j], arr[i]i += 1j -= 1arr[l], arr[j] = arr[j], arr[l]quick_sort(arr, l, j-1)quick_sort(arr, j+1, r)
應用場景
- 工程常用，STL/Java/Python底層排序
- 大規模、內存排序
7. 堆排序（Heap Sort）
原理
- 構建大頂堆，每次取堆頂與末尾交換，重建堆。
復雜度
- 時間：O(nlogn)
- 空間：O(1)
- 穩定性：不穩定
C++實現
void heapify(vector<int>& arr, int n, int i) {int largest = i, l = 2*i+1, r = 2*i+2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}
void heapSort(vector<int>& arr) {int n = arr.size();for (int i = n/2-1; i >= 0; --i)heapify(arr, n, i);for (int i = n-1; i > 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}
Python實現
def heapify(arr, n, i):largest = il, r = 2*i+1, 2*i+2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n//2-1, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]heapify(arr, i, 0)
應用場景
- 原地排序，內存受限
- TopK問題（優先隊列）
8. 計數排序（Counting Sort）
原理
- 統計每個數出現次數，累加輸出。
- 適合整數、范圍小。
復雜度
- 時間：O(n+k)
- 空間：O(n+k)
- 穩定性：穩定（優化后）
C++實現
vector<int> countingSort(const vector<int>& arr) {if (arr.empty()) return {};int minVal = *min_element(arr.begin(), arr.end());int maxVal = *max_element(arr.begin(), arr.end());vector<int> count(maxVal-minVal+1, 0);for (int num : arr) count[num-minVal]++;vector<int> res;for (int i = 0; i < count.size(); ++i)for (int j = 0; j < count[i]; ++j)res.push_back(i+minVal);return res;
}
Python實現
def counting_sort(arr):if not arr:return []min_val, max_val = min(arr), max(arr)count = [0] * (max_val - min_val + 1)for num in arr:count[num - min_val] += 1res = []for i, c in enumerate(count):res.extend([i + min_val] * c)return res
應用場景
- 整數、范圍小
- 計分、桶分布
9. 基數排序（Radix Sort）
原理
- 按位（低到高/高到低）多輪計數排序。
- 適合整數、字符串。
復雜度
- 時間：O(d(n+k))，d為位數
- 空間：O(n+k)
- 穩定性：穩定
C++實現
void radixSort(vector<int>& arr) {int maxVal = *max_element(arr.begin(), arr.end());for (int exp = 1; maxVal/exp > 0; exp *= 10) {vector<int> output(arr.size()), count(10, 0);for (int num : arr) count[(num/exp)%10]++;for (int i = 1; i < 10; ++i) count[i] += count[i-1];for (int i = arr.size()-1; i >= 0; --i) {int idx = (arr[i]/exp)%10;output[--count[idx]] = arr[i];}arr = output;}
}
Python實現
def radix_sort(arr):if not arr:return []max_val = max(arr)exp = 1while max_val // exp > 0:count = [0] * 10output = [0] * len(arr)for num in arr:count[(num // exp) % 10] += 1for i in range(1, 10):count[i] += count[i-1]for i in range(len(arr)-1, -1, -1):idx = (arr[i] // exp) % 10output[count[idx]-1] = arr[i]count[idx] -= 1arr = output[:]exp *= 10return arr
應用場景
- 大量整數、字符串排序
- 電話號碼、身份證號等
10. 桶排序（Bucket Sort）
原理
- 劃分區間到多個桶，桶內排序，合并輸出。
- 適合均勻分布、浮點數。
復雜度
- 時間：O(n)~O(n2)
- 空間：O(n+k)
- 穩定性：取決于桶內排序
C++實現
void bucketSort(vector<float>& arr) {int n = arr.size();vector<vector<float>> buckets(n);for (float num : arr) {int idx = n * num; // 假設[0,1)buckets[idx].push_back(num);}for (auto& bucket : buckets)sort(bucket.begin(), bucket.end());int idx = 0;for (auto& bucket : buckets)for (float num : bucket)arr[idx++] = num;
}
Python實現
def bucket_sort(arr):n = len(arr)buckets = [[] for _ in range(n)]for num in arr:idx = int(n * num) # 假設[0,1)buckets[idx].append(num)for bucket in buckets:bucket.sort()res = []for
)
:初識無人機控制)
