第7章：排序（Sorting）

一、导读

1.1 本章学习目标

第7章系统讲解各种排序算法的原理、实现和复杂度分析。排序是计算机科学中最基本也是研究最深入的问题之一。

本章的核心学习目标包括：

掌握简单排序算法：插入排序、希尔排序的原理和复杂度
深入理解高效排序算法：归并排序、快速排序、堆排序的实现细节
理解排序的理论下界：基于比较的排序至少需要 O(n log n)
了解非比较排序：计数排序、基数排序、桶排序
学会分析排序算法的稳定性：稳定性在实际应用中为什么重要？

1.2 为什么第七章如此重要

排序是算法分析的"试金石"。通过对比不同排序算法，你可以深入理解分治、递归、随机化等算法设计技术。排序算法也是实际编程中使用最频繁的算法之一——C标准库的 qsort、Java的 Arrays.sort、Python的 sorted() 都是精心优化的排序实现。

1.3 核心问题引导

快速排序为什么在实践中通常比归并排序更快？

为什么快速排序的最坏情况是 O(n²)？如何避免？

归并排序需要 O(n) 额外空间，能否实现原地归并？

希尔排序的增量序列如何选择？

为什么说基于比较的排序不可能突破 O(n log n)？

二、核心概念详解

7.1 简单排序算法

7.1.1 插入排序 - O(n²)

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
// 最好情况（已排序）：O(n)
// 最坏情况（逆序）：O(n²)
// 平均情况：O(n²)
// 稳定排序
// 优点：小规模或近乎有序时非常快

7.1.2 希尔排序 - O(n^(3/2)) 或更好

void shellSort(int arr[], int n) {
    // 使用 Shell 原始增量序列：N/2, N/4, ..., 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}
// 增量序列的选择影响复杂度
// Shell原始序列：O(n²)
// Hibbard序列：O(n^(3/2))
// Sedgewick序列：O(n^(4/3))
// 不稳定排序

7.2 高效排序算法

7.2.1 归并排序 - O(n log n)

void merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int p = left; p <= right; p++)
        arr[p] = temp[p];
}

void mergeSort(int arr[], int temp[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, temp, left, mid);
    mergeSort(arr, temp, mid + 1, right);
    merge(arr, temp, left, mid, right);
}

void mergeSortWrapper(int arr[], int n) {
    int *temp = (int *)malloc(n * sizeof(int));
    mergeSort(arr, temp, 0, n - 1);
    free(temp);
}
// 稳定排序
// 时间复杂度：O(n log n)（最坏、平均、最好都是）
// 空间复杂度：O(n)

7.2.2 快速排序 - 平均O(n log n)

int partition(int arr[], int low, int high) {
    // 三数取中法选择pivot
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
    if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
    if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
    swap(&arr[mid], &arr[high]);
    
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 小规模数组切换为插入排序的优化版本
void quickSortOptimized(int arr[], int low, int high) {
    if (high - low < 10) {  // 阈值可调
        insertionSort(arr + low, high - low + 1);
        return;
    }
    int pi = partition(arr, low, high);
    quickSortOptimized(arr, low, pi - 1);
    quickSortOptimized(arr, pi + 1, high);
}
// 不稳定排序
// 平均：O(n log n)
// 最坏：O(n²)（已排序数组+不选好的pivot）
// 通过三数取中+随机化可避免最坏情况

7.2.3 堆排序 - O(n log n)

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int 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(int arr[], int n) {
    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);
    }
}
// 不稳定排序
// 时间：O(n log n)
// 空间：O(1)（原地排序）

7.3 排序的理论下界

定理：任何基于比较的排序算法在最坏情况下至少需要 Ω(n log n) 次比较。

证明思路（决策树模型）：

n个元素有 n! 种排列
每次比较有2种结果（≤或>）
决策树至少有 n! 个叶节点
树高 ≥ log₂(n!) ≈ n log n（由Stirling公式）

7.4 非比较排序

// 计数排序 - O(n + k)，k为值域范围
void countingSort(int arr[], int n, int maxVal) {
    int *count = (int *)calloc(maxVal + 1, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
    
    free(count);
    free(output);
}
// 稳定排序，适用于值域较小的整数

// 基数排序 - O(d(n+k))，d为位数
void radixSort(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];
    
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        // 按当前位进行计数排序
        int *output = (int *)malloc(n * sizeof(int));
        int count[10] = {0};
        
        for (int i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
        free(output);
    }
}
// 稳定排序，适用于整数或定长字符串

三、实战案例

3.1 排序算法性能对比

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void benchmark(void (*sortFunc)(int[], int), const char *name, int n) {
    int *arr = (int *)malloc(n * sizeof(int));
    srand(42);
    for (int i = 0; i < n; i++)
        arr[i] = rand() % n;
    
    clock_t start = clock();
    sortFunc(arr, n);
    clock_t end = clock();
    
    printf("%-15s n=%-8d time=%.4f sec\n", name, n,
           (double)(end - start) / CLOCKS_PER_SEC);
    free(arr);
}

四、本章小结

算法	最好	平均	最坏	空间	稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	是
希尔排序	O(n log n)	O(n¹·⁵)	O(n²)	O(1)	否
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	是
快速排序	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(1)	否
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	是
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	是

五、思考与练习

思考题

快速排序在最坏情况下的递归深度是多少？如何避免？

为什么归并排序比快速排序更适合链表排序？

设计一个算法，在 O(n) 时间内找到数组中第k小的元素。

编程练习

实现随机化快速排序，测试其在已排序数据上的性能。

实现三路归并排序（将数组分为三部分而非两部分）。

对包含n个元素的数组，设计一个 O(n log k) 算法判断是否存在k个元素的和为0。