# 20. 排序

## 概念

**排序**是把数据按关键字从小到大（或从大到小）重新排列的过程。若排序对象能全部放进内存，称为**内部排序**；否则需要借助外存，称**外部排序**。

**稳定性**：若关键字相等的两个元素在排序后**相对次序不变**，则称该排序算法**稳定**，否则**不稳定**。判断方法：排序过程中，相等的元素是否会交换相对位置。注意稳定性与「值相同」无关，只与「相对顺序是否保持」有关。

内部排序按基本思想分四类：

1. **插入排序**：把元素插入到前面已有序子序列的正确位置。
   - **直接插入排序**：顺序往前找位置，边找边后移。稳定。
   - **折半插入排序**：用二分找插入位置，减少比较次数，但移动次数不变，仍 O(n²)。
   - **希尔排序（缩小增量排序）**：按增量 `gap` 分组做插入排序，增量逐渐缩小到 1。不稳定。
2. **交换排序**：通过交换逆序对来排序。
   - **冒泡排序**：相邻比较、逆序交换，一趟确定一个最大值沉底；可加「本趟是否交换」标志提前结束。稳定。
   - **快速排序**：选枢轴（pivot）分区，左边都比它小、右边都比它大，递归处理左右区间。不稳定。
3. **选择排序**：每趟选出剩余元素中最小（大）的放到已排序区末尾。
   - **简单选择排序**：直接扫描选出最小。不稳定（交换时可能改变相等元素顺序）。
   - **堆排序**：用大根堆，每次把堆顶（最大值）换到末尾再调整。不稳定。
4. **归并排序**：分治——把两个已有序子序列合并为一个。二路归并是经典实现。**稳定**，但需 O(n) 辅助空间。

**基数排序**（简述）：不比较关键字本身，而是按**位**（个位、十位、百位…）进行多趟「分配—收集」，配合队列/桶实现。适合关键字可以拆成若干「位」的数据（如整数、字符串）。时间复杂度 O(d(n+r))，d 为位数，r 为基数；**稳定**。

## 核心操作 / 算法

1. **直接插入**：`key=a[i]`，`j=i-1` 向前扫，`a[j]>key` 就后移，最后 `a[j+1]=key`。
2. **希尔**：`gap=n/2` 递减，对每个 `gap` 子序列做插入排序（`j>=gap && a[j-gap]>key` 时跳步移动）。
3. **冒泡**：相邻比较，`a[j]>a[j+1]` 交换；某趟无交换即已有序。
4. **快速**（挖坑法）：`pivot=a[lo]` 挖坑，右指针找小填左、左指针找大填右，两指针相遇处放回枢轴，返回枢轴位置。
5. **简单选择**：每趟找 `minIdx`，与 `a[i]` 交换。
6. **堆排序**：建堆（从最后一个非叶结点 `n/2-1` 向下调整成大根堆），然后反复「堆顶与末尾交换 → 对剩余部分调整」。
7. **二路归并**：`merge` 用辅助数组把两个有序区间合并；`mergeSort` 递归分到单元素再向上合并。

## 复杂度分析

下表为内部排序算法的完整对比（n 为元素个数，d 为基数排序位数，r 为基数）：

| 算法         | 平均                       | 最坏                | 最好       | 空间                          | 稳定性 |
| ------------ | -------------------------- | ------------------- | ---------- | ----------------------------- | ------ |
| 直接插入排序 | O(n²)                      | O(n²)               | O(n)       | O(1)                          | 稳定   |
| 折半插入排序 | O(n²)                      | O(n²)               | O(n)       | O(1)                          | 稳定   |
| 希尔排序     | O(n^1.3)（与增量序列有关） | O(n²)（取决于增量） | O(n)       | O(1)                          | 不稳定 |
| 冒泡排序     | O(n²)                      | O(n²)               | O(n)       | O(1)                          | 稳定   |
| 快速排序     | O(n log n)                 | O(n²)               | O(n log n) | O(log n)（递归栈，最坏 O(n)） | 不稳定 |
| 简单选择排序 | O(n²)                      | O(n²)               | O(n²)      | O(1)                          | 不稳定 |
| 堆排序       | O(n log n)                 | O(n log n)          | O(n log n) | O(1)                          | 不稳定 |
| 二路归并排序 | O(n log n)                 | O(n log n)          | O(n log n) | O(n)                          | 稳定   |
| 基数排序     | O(d(n+r))                  | O(d(n+r))           | O(d(n+r))  | O(n+r)                        | 稳定   |

要点记忆：

- **稳定**：直接插入、冒泡、归并、基数；**不稳定**：希尔、快排、简单选择、堆排。
- **O(n log n)**：快排（平均）、堆排、归并；三者中只有归并**稳定**。
- **空间**：归并 O(n) 辅助数组；快排 O(log n) 递归栈（最坏退化为 O(n)）；其余原地 O(1)。
- **最好 O(n)**：直接插入、冒泡（有序时）；希尔、快排最好也接近 O(n) 级别但表中按惯例给出。

## 语言实现

以下四种实现完全等价，均包含 **7 种排序算法**：直接插入、希尔、冒泡、快速（挖坑法）、简单选择、堆排序、二路归并排序。`main` 中对**同一份原始数组** `{49, 38, 65, 97, 76, 13, 27, 49}` 分别调用每种排序并打印结果，方便对比各语言写法。

### C

```c
#include <stdio.h>
#include <stdlib.h>

// 打印数组
void printArray(int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

// 1. 直接插入排序（稳定）
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) {   // 从后往前找插入位置并后移
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

// 2. 希尔排序（不稳定）
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;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

// 3. 冒泡排序（稳定，带提前结束标志）
void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;   // 本趟无交换，已经有序
    }
}

// 4. 快速排序（挖坑法分区，不稳定）
int partition(int a[], int lo, int hi) {
    int pivot = a[lo];                 // 挖坑：取出枢轴值
    while (lo < hi) {
        while (lo < hi && a[hi] >= pivot) hi--;  // 从右找比枢轴小的
        a[lo] = a[hi];                 // 填到左边的坑
        while (lo < hi && a[lo] <= pivot) lo++;  // 从左找比枢轴大的
        a[hi] = a[lo];                 // 填到右边的坑
    }
    a[lo] = pivot;                     // 枢轴归位
    return lo;
}

void quickSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

// 5. 简单选择排序（不稳定）
void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) {
            int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
        }
    }
}

// 6. 堆排序（不稳定）：对以 i 为根的子树调整为大根堆
void heapify(int a[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int 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) {
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        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--) {                        // 依次取堆顶
        int t = a[0]; a[0] = a[i]; a[i] = t;                 // 堆顶换到末尾
        heapify(a, i, 0);                                    // 重新调整
    }
}

// 7. 二路归并排序（稳定）：合并两个有序区间 [lo,mid] 与 [mid+1,hi]
void merge(int a[], int lo, int mid, int hi) {
    int len = hi - lo + 1;
    int *tmp = (int *)malloc(sizeof(int) * len);
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int m = 0; m < len; m++) a[lo + m] = tmp[m];
    free(tmp);
}

void mergeSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
}

// 拷贝数组，保证每次排序都从同一份原始数据开始
void copyArray(int src[], int dst[], int n) {
    for (int i = 0; i < n; i++) dst[i] = src[i];
}

int main() {
    int original[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int n = sizeof(original) / sizeof(original[0]);
    int *a = (int *)malloc(sizeof(int) * n);

    copyArray(original, a, n); insertionSort(a, n); printf("直接插入排序: "); printArray(a, n);
    copyArray(original, a, n); shellSort(a, n);      printf("希尔排序:     "); printArray(a, n);
    copyArray(original, a, n); bubbleSort(a, n);     printf("冒泡排序:     "); printArray(a, n);
    copyArray(original, a, n); quickSort(a, 0, n - 1); printf("快速排序:     "); printArray(a, n);
    copyArray(original, a, n); selectionSort(a, n);  printf("简单选择排序: "); printArray(a, n);
    copyArray(original, a, n); heapSort(a, n);       printf("堆排序:       "); printArray(a, n);
    copyArray(original, a, n); mergeSort(a, 0, n - 1); printf("归并排序:     "); printArray(a, n);

    free(a);
    return 0;
}
```

### C++

```C++
#include <iostream>
#include <vector>
using namespace std;

// 打印数组
void printArray(const vector<int>& a) {
    for (int x : a) cout << x << " ";
    cout << endl;
}

// 1. 直接插入排序（稳定）
void insertionSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

// 2. 希尔排序（不稳定）
void shellSort(vector<int>& a) {
    int n = (int)a.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i], j = i;
            while (j >= gap && a[j - gap] > key) { a[j] = a[j - gap]; j -= gap; }
            a[j] = key;
        }
    }
}

// 3. 冒泡排序（稳定，带提前结束标志）
void bubbleSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
        if (!swapped) break;
    }
}

// 4. 快速排序（挖坑法，不稳定）
int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[lo];                 // 挖坑
    while (lo < hi) {
        while (lo < hi && a[hi] >= pivot) hi--;
        a[lo] = a[hi];
        while (lo < hi && a[lo] <= pivot) lo++;
        a[hi] = a[lo];
    }
    a[lo] = pivot;
    return lo;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

// 5. 简单选择排序（不稳定）
void selectionSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

// 6. 堆排序（不稳定）
void heapify(vector<int>& a, int n, int i) {
    int largest = i, 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(vector<int>& a) {
    int n = (int)a.size();
    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); }
}

// 7. 二路归并排序（稳定）
void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int m = 0; m < (int)tmp.size(); m++) a[lo + m] = tmp[m];
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
}

int main() {
    vector<int> original = {49, 38, 65, 97, 76, 13, 27, 49};

    vector<int> a = original; insertionSort(a); cout << "直接插入排序: "; printArray(a);
    a = original; shellSort(a);      cout << "希尔排序:     "; printArray(a);
    a = original; bubbleSort(a);     cout << "冒泡排序:     "; printArray(a);
    a = original; quickSort(a, 0, (int)a.size() - 1); cout << "快速排序:     "; printArray(a);
    a = original; selectionSort(a);  cout << "简单选择排序: "; printArray(a);
    a = original; heapSort(a);       cout << "堆排序:       "; printArray(a);
    a = original; mergeSort(a, 0, (int)a.size() - 1); cout << "归并排序:     "; printArray(a);

    return 0;
}
```

### Java

```java
public class SortDemo {
    // 打印数组
    static void printArray(int[] a) {
        for (int x : a) System.out.print(x + " ");
        System.out.println();
    }

    // 1. 直接插入排序（稳定）
    static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
            a[j + 1] = key;
        }
    }

    // 2. 希尔排序（不稳定）
    static void shellSort(int[] a) {
        for (int gap = a.length / 2; gap > 0; gap /= 2)
            for (int i = gap; i < a.length; i++) {
                int key = a[i], j = i;
                while (j >= gap && a[j - gap] > key) { a[j] = a[j - gap]; j -= gap; }
                a[j] = key;
            }
    }

    // 3. 冒泡排序（稳定，带提前结束标志）
    static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < a.length - 1 - i; j++)
                if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = true; }
            if (!swapped) break;
        }
    }

    // 4. 快速排序（挖坑法，不稳定）
    static int partition(int[] a, int lo, int hi) {
        int pivot = a[lo];                 // 挖坑
        while (lo < hi) {
            while (lo < hi && a[hi] >= pivot) hi--;
            a[lo] = a[hi];
            while (lo < hi && a[lo] <= pivot) lo++;
            a[hi] = a[lo];
        }
        a[lo] = pivot;
        return lo;
    }

    static void quickSort(int[] a, int lo, int hi) {
        if (lo < hi) {
            int p = partition(a, lo, hi);
            quickSort(a, lo, p - 1);
            quickSort(a, p + 1, hi);
        }
    }

    // 5. 简单选择排序（不稳定）
    static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < a.length; j++)
                if (a[j] < a[minIdx]) minIdx = j;
            if (minIdx != i) { int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t; }
        }
    }

    // 6. 堆排序（不稳定）
    static void heapify(int[] a, int n, int i) {
        int largest = i, 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) { int t = a[i]; a[i] = a[largest]; a[largest] = t; heapify(a, n, largest); }
    }

    static void heapSort(int[] a) {
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);  // 建大根堆
        for (int i = n - 1; i > 0; i--) { int t = a[0]; a[0] = a[i]; a[i] = t; heapify(a, i, 0); }
    }

    // 7. 二路归并排序（稳定）
    static void merge(int[] a, int lo, int mid, int hi) {
        int len = hi - lo + 1;
        int[] tmp = new int[len];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi)  tmp[k++] = a[j++];
        for (int m = 0; m < len; m++) a[lo + m] = tmp[m];
    }

    static void mergeSort(int[] a, int lo, int hi) {
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            mergeSort(a, lo, mid);
            mergeSort(a, mid + 1, hi);
            merge(a, lo, mid, hi);
        }
    }

    public static void main(String[] args) {
        int[] original = {49, 38, 65, 97, 76, 13, 27, 49};

        int[] a = original.clone(); insertionSort(a); System.out.print("直接插入排序: "); printArray(a);
        a = original.clone(); shellSort(a);      System.out.print("希尔排序:     "); printArray(a);
        a = original.clone(); bubbleSort(a);     System.out.print("冒泡排序:     "); printArray(a);
        a = original.clone(); quickSort(a, 0, a.length - 1); System.out.print("快速排序:     "); printArray(a);
        a = original.clone(); selectionSort(a);  System.out.print("简单选择排序: "); printArray(a);
        a = original.clone(); heapSort(a);       System.out.print("堆排序:       "); printArray(a);
        a = original.clone(); mergeSort(a, 0, a.length - 1); System.out.print("归并排序:     "); printArray(a);
    }
}
```

### Python

```python
# ---------- 7 种排序算法 ----------

def insertion_sort(a):
    """1. 直接插入排序（稳定）"""
    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


def shell_sort(a):
    """2. 希尔排序（不稳定）"""
    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


def bubble_sort(a):
    """3. 冒泡排序（稳定，带提前结束标志）"""
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break


def _partition(a, lo, hi):
    """快速排序挖坑法分区"""
    pivot = a[lo]                # 挖坑
    while lo < hi:
        while lo < hi and a[hi] >= pivot:
            hi -= 1
        a[lo] = a[hi]
        while lo < hi and a[lo] <= pivot:
            lo += 1
        a[hi] = a[lo]
    a[lo] = pivot
    return lo


def quick_sort(a, lo, hi):
    """4. 快速排序（不稳定）"""
    if lo < hi:
        p = _partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)


def selection_sort(a):
    """5. 简单选择排序（不稳定）"""
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]


def _heapify(a, n, i):
    """堆排序：对以 i 为根的子树调整为大根堆"""
    largest = i
    l, r = 2 * i + 1, 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 heap_sort(a):
    """6. 堆排序（不稳定）"""
    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)


def _merge(a, lo, mid, hi):
    """归并排序：合并两个有序区间 [lo,mid] 与 [mid+1,hi]"""
    tmp = []
    i, j = lo, mid + 1
    while i <= mid and j <= hi:
        if a[i] <= a[j]:
            tmp.append(a[i]); i += 1
        else:
            tmp.append(a[j]); j += 1
    while i <= mid:
        tmp.append(a[i]); i += 1
    while j <= hi:
        tmp.append(a[j]); j += 1
    a[lo:hi + 1] = tmp


def merge_sort(a, lo, hi):
    """7. 二路归并排序（稳定）"""
    if lo < hi:
        mid = lo + (hi - lo) // 2
        merge_sort(a, lo, mid)
        merge_sort(a, mid + 1, hi)
        _merge(a, lo, mid, hi)


if __name__ == "__main__":
    original = [49, 38, 65, 97, 76, 13, 27, 49]

    a = original[:]; insertion_sort(a); print("直接插入排序:", a)
    a = original[:]; shell_sort(a);     print("希尔排序:    ", a)
    a = original[:]; bubble_sort(a);    print("冒泡排序:    ", a)
    a = original[:]; quick_sort(a, 0, len(a) - 1); print("快速排序:    ", a)
    a = original[:]; selection_sort(a); print("简单选择排序:", a)
    a = original[:]; heap_sort(a);      print("堆排序:      ", a)
    a = original[:]; merge_sort(a, 0, len(a) - 1); print("归并排序:    ", a)
```