---
# System prepended metadata

title: 【5-2】排序演算法 & sort

---

# 【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 子柚筆