第 8 章 · 排序

排序 = 把无序变有序；评价维度：时间、空间、稳定性。

8.1 三大基础排序 O(n²)

// 冒泡：相邻交换，每轮把最大「冒」到末尾；稳定
void bubble(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]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; }
}

// 选择：每轮选最小放前面；不稳定（交换会跨过相等元素）
void select(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[m]) m = j;
        int t = a[i]; a[i] = a[m]; a[m] = t;
    }
}

// 插入：把新元素插进已排序前缀；稳定，接近有序时近乎 O(n)
void insert(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int k = a[i], j = i - 1;
        while (j >= 0 && a[j] > k) { a[j + 1] = a[j]; j--; }
        a[j + 1] = k;
    }
}

8.2 快排：分治 + 原地划分 O(n log n)

int part(int *a, int lo, int hi) {
    int p = a[lo], i = lo, j = hi;
    while (i < j) {
        while (i < j && a[j] >= p) j--;
        a[i] = a[j];
        while (i < j && a[i] <= p) i++;
        a[j] = a[i];
    }
    a[i] = p; return i;
}
void quick(int *a, int lo, int hi) {
    if (lo >= hi) return;
    int m = part(a, lo, hi);
    quick(a, lo, m - 1); quick(a, m + 1, hi);
}

平均 O(n log n)，最坏 O(n²)（已有序 + 取首元素为轴，可用随机化/三数取中缓解）；不稳定。

8.3 归并：分治 + 合并 O(n log n) 稳定

void merge(int *a, int lo, int mid, int hi, int *tmp) {
    int i = lo, j = mid + 1, k = lo;
    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 (i = lo; i <= hi; i++) a[i] = tmp[i];
}
void msort(int *a, int lo, int hi, int *tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    msort(a, lo, mid, tmp); msort(a, mid + 1, hi, tmp);
    merge(a, lo, mid, hi, tmp);
}

稳定但需 O(n) 辅助数组——空间换稳定性。适合外排序（磁盘）。

8.4 堆排 / 希尔 / 计数

• 堆排：建大顶堆（第 5 章）→ 反复取堆顶放末尾，O(n log n)，原地，不稳定。
• 希尔：按增量分组做插入排序，增量递减到 1，平均接近 O(n^1.3)，不稳定。
• 计数：统计每个值出现次数再展开，O(n+k)，稳定，但只适合整数且值域小。

对比：八大排序总表——

排序	最好	平均	最坏	空间	稳定
冒泡	O(n)	O(n²)	O(n²)	O(1)	稳定
选择	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入	O(n)	O(n²)	O(n²)	O(1)	稳定
希尔	O(n)	O(n^1.3)	O(n²)	O(1)	不稳定
快排	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定

取舍：数据小或基本有序用插入；要求稳定且数据量大用归并；内存受限要原地用堆排；通用场景用快排（随机化轴）。