# 【5-2】排序演算法 & sort
排序，在日常生活中也很常見，國小老師會教我們照身高矮到高排路隊，或者是座號小到大。
我們舉最簡單的例子，座號從小到大排序，假設班上現在有 $n$ 位學生，目前隨機排成一個路隊，要怎麼讓他們按照一個「規則」來排成小到大呢？
## 1. 選擇排序（Selection Sort）
**原理**：每輪找出最小值，放到前面的位置。
* 時間複雜度：$O(n^2)$
* 空間複雜度：$O(1)$
```cpp
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 假設目前的為最小值，紀錄 index
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIndex]) { // 從自己往後，發現比目前更小的就記錄 index
minIndex = j;
}
}
swap(a[i], a[minIndex]); // 交換
}
}
```
### Python對照
```python=
def selectionSort(a):
for i in range(len(a) - 1):
min_index = i
for j in range(i + 1, len(a)):
if a[j] < a[min_index]:
min_index = j
a[i], a[min_index] = a[min_index], a[i]
```
---
## 2. 氣泡排序（Bubble Sort）
**原理**：相鄰兩數比較，大的往後冒泡，逐輪排序。
* 時間複雜度：$O(n^2)$，最佳 $O(n)$
* 空間複雜度：$O(1)$
```cpp
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) { // 相鄰兩數比較，若該位大於下一位，則兩者交換位置
swap(a[j], a[j + 1]);
}
}
}
}
```
### Python對照
```python=
def bubbleSort(a):
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
```
---
## 3. 插入排序（Insertion Sort）
**原理**：每次將一個數插入前面已排序的區段。
* 時間複雜度：$O(n^2)$，最佳 $O(n)$
* 空間複雜度：$O(1)$
```cpp
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i]; // 紀錄目前要排序的資料
int j = i - 1;
while (j >= 0 && a[j] > key) { // 確保邊界條件，以及嘗試尋找第一個小於 key 的位置
a[j + 1] = a[j]; // 挪動一格，供 key 插入用
j--;
}
a[j + 1] = key; // 插入 key
}
}
```
### Python對照
```python=
def insertionSort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
```
---
## 4. 希爾排序（Shell Sort）
**原理**：先比較距離較遠的元素（gap），再逐漸縮小距離至 1，最終完成排序。是插入排序的改良版。
* 時間複雜度：$O(n^{1.3})$（視 gap 策略而定）
* 空間複雜度：$O(1)$
```cpp
void shellSort(int a[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) { // 每次砍半（二分）
for (int i = gap; i < n; i++) {
int key = a[i]; // 要插入的數字
int j = i - gap;
while (j >= 0 && a[j] > key) {
a[j + gap] = a[j]; // 往右移動
j -= gap;
}
a[j + gap] = key; // 插入 key
}
}
}
```
### Python對照
```python=
def shellSort(a):
n = len(a)
gap = n // 2
while gap > 0:
for i in range(gap, n):
key = a[i]
j = i
while j >= gap and a[j - gap] > key:
a[j] = a[j - gap]
j -= gap
a[j] = key
gap //= 2
```
---
## 5. 快速排序（Quick Sort）
**原理**：選一個 pivot，把比它小的放左邊，比它大的放右邊，再對左右兩邊遞迴排序。
* 時間複雜度：$O(n \log n)$，最壞 $O(n^2)$
* 空間複雜度：$O(\log n)$
```cpp
int partition(int a[], int left, int right) {
int pivot = a[right]; // 選最後一個當 pivot
int i = left - 1;
for (int j = left; j < right; j++) {
if (a[j] < pivot) {
i++;
swap(a[i], a[j]); // 把小於 pivot 的換到左邊
}
}
swap(a[i + 1], a[right]); // 把 pivot 放中間正確位置
return i + 1; // 回傳 pivot 的位置
}
void quickSort(int a[], int left, int right) {
if (left < right) {
int pi = partition(a, left, right); // 劃分陣列
quickSort(a, left, pi - 1); // 左邊遞迴排序
quickSort(a, pi + 1, right); // 右邊遞迴排序
}
}
```
### Python對照
```python=
def partition(a, left, right):
pivot = a[right]
i = left - 1
for j in range(left, right):
if a[j] < pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[right] = a[right], a[i + 1]
return i + 1
def quickSort(a, left, right):
if left < right:
pi = partition(a, left, right)
quickSort(a, left, pi - 1)
quickSort(a, pi + 1, right)
```
---
## 6. 合併排序（Merge Sort）
**原理**：把陣列一分為二，分別排序後，再將兩部分合併。
* 時間複雜度：$O(n \log n)$
* 空間複雜度：$O(n)$
```cpp
void merge(int a[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2]; // 左右兩個子陣列
for (int i = 0; i < n1; i++) L[i] = a[l + i];
for (int i = 0; i < n2; i++) R[i] = a[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) a[k++] = L[i++];
else a[k++] = R[j++];
}
while (i < n1) a[k++] = L[i++]; // 左邊剩的補上
while (j < n2) a[k++] = R[j++]; // 右邊剩的補上
}
void mergeSort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2; // 中點
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}
```
### Python對照
```python=
def merge(a, l, m, r):
L = a[l:m+1]
R = a[m+1:r+1]
i = j = 0
k = l
while i < len(L) and j < len(R):
if L[i] <= R[j]:
a[k] = L[i]
i += 1
else:
a[k] = R[j]
j += 1
k += 1
a[k:r+1] = L[i:] + R[j:]
def mergeSort(a, l, r):
if l < r:
m = (l + r) // 2
mergeSort(a, l, m)
mergeSort(a, m + 1, r)
merge(a, l, m, r)
```
---
## 7. 堆積排序（Heap Sort）
**原理**：先建成最大堆，每次把最大值（根節點）拿出來放到最後，重建堆。
* 時間複雜度：$O(n \log n)$
* 空間複雜度：$O(1)$
```cpp
void heapify(int a[], int n, int i) {
int largest = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest != i) {
swap(a[i], a[largest]);
heapify(a, n, largest); // 遞迴調整子樹
}
}
void heapSort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // 建堆
for (int i = n - 1; i >= 0; i--) {
swap(a[0], a[i]); // 最大值移到最後
heapify(a, i, 0); // 重建堆
}
}
```
### Python對照
```python=
def heapify(a, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and a[l] > a[largest]:
largest = l
if r < n and a[r] > a[largest]:
largest = r
if largest != i:
a[i], a[largest] = a[largest], a[i]
heapify(a, n, largest)
def heapsort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1):
heapify(a, n, i)
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0]
heapify(a, i, 0)
```
---
## 8. 計數排序（Counting Sort）
**原理**：計算每個數字出現的次數，依序重建陣列。
* 時間複雜度：$O(n + k)$，$k$ 為最大數值
* 空間複雜度：$O(n + k)$
```cpp
void countingSort(int a[], int n) {
int maxVal = *max_element(a, a + n);
int count[maxVal + 1] = {0};
for (int i = 0; i < n; i++) count[a[i]]++; // 統計次數
int index = 0;
for (int i = 0; i <= maxVal; i++) {
while (count[i]--) a[index++] = i; // 根據次數填回去
}
}
```
### Python對照
```python=
def countingsort(a):
if not a:
return
maxVal = max(a)
count = [0] * (maxVal + 1)
for x in a:
count[x] += 1
index = 0
for i, c in enumerate(count):
for _ in range(c):
a[index] = i
index += 1
```
---
看了這麼多，頭要暈了吧，我也覺得很累，所以我們用 C++ STL 提供的 `sort()` 函式來排序吧：
## sort
**原理**：C++ STL 提供的 `sort()` 使用的是一種混合排序（IntroSort），結合了 **快速排序、堆積排序與插入排序** 的優點。
* 時間複雜度：平均 $O(n \log n)$，最壞 $O(n \log n)$
* 空間複雜度：$O(\log n)$
```cpp
sort(a.begin(), a.end()); // 升冪排序
sort(a.begin(), a.end(), greater<int>()); // 降冪排序
sort(a.begin(), a.end(), compare); // 使用自定義的排序（寫在副函式）
```
```cpp
bool compare(int a, int b) {
return a > b; // a 大於 b 時返回 true，實現降冪排序
}
```
注意！如果是 C 陣列，就要使用指標的寫法，不能使用迭代器，可以參考以下寫法：
```cpp
sort(a, a + n); // 對 a[0] ~ a[n-1] 升冪排序
```
### Python對照
```python=
a = [5, 3, 8, 1]
# 升冪排序
a.sort()
# 降冪排序
a.sort(reverse=True)
# 使用 sorted() 函式（不改變原串列）
b = sorted(a)
# 自訂排序（以字串長度排序為例）
words = ['apple', 'banana', 'cherry', 'date']
words.sort(key=len)
```
---
聯絡方式：codecodefunny@gmail.com
最後編修時間：2025/08/24 子柚筆
Sign in with Wallet
Connect another wallet