【数据结构与算法体系】之排序算法

系列学习路线图

flowchart TD
    A([数据结构与算法]) --> B[基础数据结构]

    subgraph B["基础数据结构"]
        b1["表·栈·队列"] & b2["树（BST·红黑树）"] & b3["散列 Hash Table"] & b4["优先队列·堆"]
    end

    B --> C[高级数据结构]

    subgraph C["高级数据结构"]
        c1["斐波那契堆"] & c2["van Emde Boas 树"] & c3["不相交集·并查集"]
    end

    C --> D[算法设计]

    subgraph D["算法设计范式"]
        d1["排序算法"] --> d2["摊还分析"]
        d2 --> d3["贪心算法"]
        d3 --> d4["动态规划"]
    end

    D --> E[图算法]

    subgraph E["图算法（由浅入深）"]
        e1["① 基本篇"] --> e2["② 最小生成树"]
        e2 --> e3["③ 单源最短路径"]
        e3 --> e4["④ 所有结点对最短路径"]
        e4 --> e5(["⑤ 最大流 ✅"])
    end

    style A fill:#fbbf24,stroke:#f59e0b,color:#000
    style e5 fill:#10b981,stroke:#059669,color:#fff

---

一、排序算法的分类与评价标准

排序是计算机科学中最基础的操作之一，也是被研究得最透彻的算法领域。根据数据是否全部加载到内存，排序算法分为内排序（所有数据在内存中完成排序）和外排序（数据量太大，需要借助外部存储）。本文聚焦于内排序的经典算法，但也深入讨论部分外排序的核心技术。

评价一个排序算法主要有五个维度：

时间复杂度：最好、最坏和平均情况下的比较和移动次数。基于比较的排序算法在最坏情况下至少需要Ω(N log N)次比较——这是信息论的下界，通过决策树模型可以严格证明：N个元素的排列有N!种可能，每种排列对应决策树的一个叶子节点。高度为h的二叉树最多有2^h个叶子节点，因此2^h ≥ N!，即h ≥ log₂(N!)。根据斯特林近似公式 log₂(N!) ≈ N log₂ N - N log₂ e，即Ω(N log N)。归并排序和堆排序在最坏情况下达到了这个理论下界，因此它们是最优的比较排序算法。

空间复杂度：除输入数据外所需的额外内存。原地排序（In-Place）算法的空间复杂度为O(1)。注意递归调用的栈深度也应计入空间复杂度——例如快速排序的O(log N)栈空间。

稳定性：排序后相等元素的相对顺序是否保持不变。稳定性在多关键字排序中至关重要——例如先按成绩排序，再按姓名排序（同分的人内部需保持姓名的字典序）。基数排序依赖于每一轮排序的稳定性。

适应性（Adaptivity）：算法是否能利用输入数据已有的部分有序性。插入排序和TimSort是典型的高适应性算法——在部分有序的数据上可以达到O(N)的复杂度。而选择排序和堆排序则完全不适应，无论输入如何都执行固定数量的比较。

实践性能：理论上同样的渐近复杂度在实践中可能差距显著，原因包括缓存局部性（Cache Locality）、分支预测（Branch Prediction）、内存分配/拷贝开销等。快速排序的常数因子通常小于归并排序（约2-3倍），使其在实践中是默认首选的通用排序算法。

二、插入排序与希尔排序——小规模与部分有序的利器

插入排序（Insertion Sort）：将数组分为”已排序”和”未排序”两部分，每次将未排序部分的第一个元素插入到已排序部分的正确位置。插入排序是稳定和原地的。

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; 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²)。插入排序在实践中对小规模数组（N < 50）非常高效——常数因子极小，缓存友好（扫描连续内存），且对于”几乎有序”的数组性能接近O(N)。这使得它成为更复杂排序算法（如TimSort、快速排序在小分区时的回退）的底层原语。

二分插入排序：在寻找插入位置时使用二分查找，将比较次数从O(N)降到O(log N)，但元素移动次数仍是O(N)，因此总体时间复杂度不变。对于比较代价很高的数据类型（如长字符串排序），二分插入排序有实际优势。

希尔排序（Shell Sort）：插入排序的泛化。使用递增的间隔序列（Gap Sequence），对每个间隔执行跨步的插入排序。随着间隔逐渐缩小，数组变得越来越有序，最后一步（gap=1时）就是标准的插入排序，但因为此时数组已基本有序，实际只需很少的比较和移动。

void shellSort(int[] arr) {
    int n = arr.length;
    // 使用 Sedgewick 增量序列
    int h = 1;
    while (h < n / 3) h = 3 * h + 1;  // 1, 4, 13, 40, 121, ...
    
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= h && arr[j - h] > key) {
                arr[j] = arr[j - h];
                j -= h;
            }
            arr[j] = key;
        }
        h /= 3;
    }
}

希尔排序的时间复杂度取决于间隔序列的选择。Hibbard序列（1, 3, 7, 15, …, 2^k-1）的最坏复杂度为O(N^(3/2))；Sedgewick序列的最坏复杂度为O(N^(4/3))。实际上，对于中等规模的数组（N < 10^5），希尔排序的性能非常具有竞争力。它是不稳定排序。尽管希尔排序的理论渐近复杂度不如O(N log N)算法，但代码极其简洁且无需额外空间，在嵌入式系统和资源受限环境中仍有价值。

三、快速排序——深度剖析

快速排序（QuickSort）是实践中使用最广泛的排序算法。它采用分治策略：选择一个基准元素（Pivot），将数组划分为两部分——左半部所有元素小于等于Pivot，右半部所有元素大于等于Pivot；然后递归地对左右两部分进行快速排序。

快速排序的核心是分区（Partition）算法。

Lomuto分区方案：选择最后（或最右）元素为Pivot。维护指针i，使得[low, i]中的元素始终 ≤ pivot，[i+1, j)中的元素始终 > pivot。

public class QuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选择最右元素为基准
        int i = low - 1;        // i指向小于pivot的区域的最后一个元素
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high); // 将pivot放到正确位置
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Hoare分区方案：使用双向扫描——左指针从左寻找 ≥ pivot的元素，右指针从右寻找 ≤ pivot的元素，找到后交换。Hoare方案的平均交换次数约为Lomuto方案的1/3，但实现更精妙，且最终pivot的位置不一定是分区边界（需要额外的边界确定逻辑）。Hoare分区是C语言标准库qsort的基础。

// Hoare分区
int partitionHoare(int[] arr, int low, int high) {
    int pivot = arr[low]; // 或随机选择后交换到low
    int i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;  // 返回分界点
        swap(arr, i, j);
    }
}

三向分区（Three-Way Partition / Dutch National Flag）：当数组中存在大量重复元素时，标准分区会将重复元素分散到左右两边，导致大量的等价比较。三向分区将数组划分为 < pivot、== pivot、> pivot 三部分，只在严格小于和严格大于的部分上递归。这使得含有大量重复元素的数组排序可达到O(N)：

void sort3Way(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = arr[low];
    int lt = low;      // arr[low..lt-1] < pivot
    int gt = high;     // arr[gt+1..high] > pivot
    int i = low;       // arr[lt..i-1] == pivot
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt++, i++);
        } else if (arr[i] > pivot) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    sort3Way(arr, low, lt - 1);
    sort3Way(arr, gt + 1, high);
}

Pivot选择策略深刻影响快速排序的性能：

• 固定Pivot（如始终选最右元素）：在有序数组上退化为O(N²)，这是不可接受的。
• 随机化Pivot：在分区前随机选择一个元素与最右元素交换。数学上可证明期望时间复杂度为O(N log N)，且最坏情况概率极低（约为作业调度中所有N!排列等概率出现的概率）。这是最常用的工程策略。
• Median-of-3：取low、mid、high三个位置的元素，选中位数作为Pivot。在有序数据上可达到O(N log N)，但对抗性构造的输入仍可制造O(N²)情况。
• BFPRT（Median of Medians）：可以在O(N)时间内找到确定性的中位数（将数组分成5个一组的N/5组，递归地找到各组中位数的中位数）。但BFPRT的常数因子太大（约20-30倍），实践中不如随机化Pivot。仅在需要确定性的线性时间选择时使用。
• Ninther（Tukey’s Ninther）：取三组每组三个元素的中位数，再取这三个中位数的中位数，是一种鲁棒的Pivot估计策略。

尾递归优化（Tail Recursion Optimization）：快速排序的标准递归实现有两次递归调用。可以优化为只对较小的分区递归，较大的分区通过循环迭代处理：

void sortOptimized(int[] arr, int low, int high) {
    while (low < high) {
        int p = partition(arr, low, high);
        if (p - low < high - p) {
            sortOptimized(arr, low, p - 1);
            low = p + 1;
        } else {
            sortOptimized(arr, p + 1, high);
            high = p - 1;
        }
    }
}

这确保递归深度不超过O(log N)，即使在最坏情况下也不会栈溢出。

Dual-Pivot QuickSort（Java 7+ Arrays.sort对原始类型的默认算法）：选择两个Pivot（p1 ≤ p2），将数组分为三段（< p1, p1 ≤ x ≤ p2, > p2）。两个Pivot增加了每次分区的比较次数（更多条件判断），但减少了递归深度（以3为底的分治而非以2为底）和交换次数。实际基准测试中，Dual-Pivot QuickSort比单Pivot版本快约10-15%。

快速排序是不稳定的——分区过程中的交换会打乱相等元素的相对顺序。空间复杂度为O(log N)（递归调用栈的深度）。

四、归并排序及其变种

归并排序（Merge Sort）是分治思想的经典体现：将数组递归地一分为二，直到子数组长度为1（天然有序）；然后将两个有序子数组合并为一个有序数组。

public class MergeSort {
    public static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            sort(arr, left, mid, temp);
            sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, k);
    }
}

归并排序的时间复杂度在所有情况下都是O(N log N)。归并排序是稳定的——合并时当左右元素相等时，优先取左边的元素，保持了原始顺序。空间复杂度为O(N)（需要临时数组），这是归并排序相比快速排序的主要劣势。

自底向上归并排序：摒弃递归，直接从长度为1的子数组开始迭代合并。避免了递归开销，且自然适合外排序场景。

void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min(left + 2 * size - 1, n - 1);
            merge(arr, left, mid, right, temp);
        }
    }
}

反转对计数（Inversion Count）：归并排序可以自然地扩展为计算数组中的逆序对数量——在合并过程中，当右边的元素被放入临时数组时，左边剩余的所有元素都与该元素构成逆序对。时间复杂度O(N log N)。

long mergeAndCount(int[] arr, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    long count = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i + 1); // 右边的元素与左边剩余所有元素构成逆序
        }
    }
    // ... 处理剩余元素
    return count;
}

外排序（External Sort）：当数据量超出内存容量时使用。第一阶段（Run Generation）：将数据分块读入内存，每块在内存中排序后写回磁盘，形成多个有序的”归并段”（Run）。第二阶段（Multi-way Merge）：使用最小堆从所有归并段中读取数据，每次取出最小值输出。如果有K个归并段，使用大小为K的最小堆（或败者树，Loser Tree），总时间复杂度O(N log K)。数据库的ORDER BY在数据量大于sort_buffer_size时的排序操作，使用的就是基于归并排序的外排序。关键优化包括：增加归并段的大小（使用替换选择算法）、调整归并路的数量以匹配I/O带宽、使用预读缓冲区减少I/O等待。

五、堆排序的深入分析

堆排序（Heap Sort）利用堆数据结构的选择性质进行排序。首先将数组构建为最大堆（Build-Heap），然后重复执行”取出堆顶（最大值）→放到数组末尾→堆大小减一→堆顶下沉（SiftDown）”。

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        // 构建最大堆：从最后一个非叶子节点开始下沉
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        // 逐一取出堆顶
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);     // 堆顶与末尾交换
            siftDown(arr, i, 0); // 堆大小减1，下沉新堆顶
        }
    }
    
    private static void siftDown(int[] arr, int heapSize, int i) {
        int value = arr[i];
        int half = heapSize >>> 1;
        while (i < half) { // 非叶子节点
            int child = (i << 1) + 1;
            int right = child + 1;
            if (right < heapSize && arr[right] > arr[child]) {
                child = right;
            }
            if (value >= arr[child]) break;
            arr[i] = arr[child];
            i = child;
        }
        arr[i] = value;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

注意上面的siftDown实现使用了一个常见优化——将目标值暂存起来，只在确定最终位置后才赋值，减少了一半的交换操作（因为每次下沉不需要交换赋值，只需将子节点上移即可）。

堆排序的时间复杂度在所有情况下都是O(N log N)。Build-Heap的O(N)证明是面试中的经典考点。分析：考虑一个高度为h的满二叉堆，第k层有2^k个节点，每个节点最多下沉(h-k)次。总下沉次数为 Σ(k从0到h) (h-k) × 2^k。令 j = h - k，则求和变为 Σ(j从0到h) j × 2^(h-j) = 2^h × Σ(j × 2^(-j))。Σ(j/2^j) 收敛于2，因此总和为 O(2^h) = O(N)。直观理解：绝大多数节点在下层（靠近叶子），下沉距离很短；只有极少数上层节点需要长距离下沉。

堆排序是不稳定的，堆顶与末尾的交换可能破坏相等元素的相对顺序。空间复杂度为O(1)，是原地排序。堆排序的理论优势在于最坏情况也是O(N log N)且空间常数额外。但在实践中，由于缓存局部性差（堆的节点访问是跳跃的，siftDown需要频繁地在父子节点间远距离跳转，而快速排序是线性扫描），通常比快速排序慢2-3倍。

SmoothSort（平顺排序，Dijkstra发明）：堆的一种变体，利用Leonardo数（类似斐波那契数）构造多叉堆，使得在已经有序的输入上时间复杂度为O(N)，最坏情况为O(N log N)。它结合了堆排序和插入排序的优点，但实现极其复杂，几乎没有工程采用。

六、线性时间排序算法

基于比较的排序有Ω(N log N)的下界，但通过利用数据本身的特性，某些排序算法可以达到线性时间。

计数排序（Counting Sort）：适用于取值范围较小的整数。统计每个值出现的次数，然后计算累积分布，最后直接将元素放到正确位置。在输出阶段，为确保稳定性，需要从后向前遍历原数组，根据累积分布数组确定每个元素的最终位置并将其放入输出数组。

// 稳定的计数排序（可配合基数排序）
void countingSortStable(int[] arr, int maxVal) {
    int n = arr.length;
    int[] count = new int[maxVal + 1];
    int[] output = new int[n];
    
    for (int v : arr) count[v]++;
    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]]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
}

时间复杂度O(N + K)，K为取值范围大小。空间复杂度O(N + K)。稳定。当K = O(N)时，计数排序是线性时间的。当K远大于N时，计数排序不再适用——此时基数排序可能更合适。

基数排序（Radix Sort）：从最低位（LSD）或最高位（MSD）开始，逐位使用稳定的排序算法。朴素实现每位使用计数排序（取值范围0-9）。

void radixSortLSD(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] output = new int[arr.length];
    
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int[] count = new int[10];
        for (int v : arr) count[(v / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

基数排序优化的关键技巧：

• 以2的幂为基数：对32位整数排序，以8位（256）为基数只需要4轮，以16位（65536）为基数只需要2轮。基数越大，轮数越少，但计数数组越大。最优基数由L1缓存大小决定——计数数组应能放入L1缓存（通常32KB），因此256（8位）是常见的最优选择。
• MSD基数排序：从最高位开始，递归地对每个桶应用基数排序。优势在于可以提前终止（当桶内元素较少时切换为插入排序），且内存访问更具缓存友好性。广泛用于字符串排序（如Java的Arrays.sort(String[])使用MSD基数排序）。
• 原地基数排序（American Flag Sort）：在MSD基数排序基础上，每轮在桶内就地重排元素位置，避免分配额外的输出数组。类似于快速排序的分区，但分区依据是键的某一位。

桶排序（Bucket Sort）：将数据均匀分布到若干个桶中，每个桶内使用其他排序算法排序，然后按桶的顺序合并。如果桶的数量与元素数量相近且数据均匀分布，平均时间复杂度为O(N)。最坏情况（所有元素落到同一个桶中）退化为桶内排序算法的复杂度。桶排序对输入分布敏感——如果数据分布不均，某些桶可能很大（桶内排序退化），某些可能为空（浪费空间）。更好的策略是使用自适应桶大小，例如根据数据密度动态调整桶的边界。

七、TimSort —— 工业级的自适应排序算法

TimSort是Python（自2.3版本）和Java（自JDK 7，用于Arrays.sort(Object[])和Collections.sort()）使用的排序算法，由Tim Peters于2002年为Python设计。它结合了归并排序和插入排序的思想，并专门优化了实际数据中常见的部分有序模式。

核心参数：MIN_RUN = 32（或根据数组大小动态计算，范围在16到64之间）。将数组划分为若干Run（有序段），每个Run至少MIN_RUN个元素。如果自然Run太短，使用二分插入排序扩展到MIN_RUN。

Run的识别与扩展：从当前位置开始，识别一个自然的有序段（递增或递减，递减段反转方向）。递增Run中相等的元素保持稳定性。如果自然Run长度小于MIN_RUN，取后续MIN_RUN个元素，使用二分插入排序扩展到指定长度。

Galloping模式：当合并两个Run A和B时，如果连续从某个Run中取出多个元素（阈值通常为7），算法猜测该Run的元素倾向于连续出现，切换到Galloping模式——使用指数搜索（先1步、再2步、再4步……）快速定位B中元素在A中的插入范围，然后通过二分查找精确定位。这在数据高度有序时可以大幅减少比较次数（从O(N+M)降到O(log N + log M + K)，其中K是实际需要移动的元素数）。

合并策略：TimSort维护一个Run栈，当栈顶三个Run满足特定条件时触发合并。具体规则：保持栈中Run长度满足 A > B + C 和 B > C（其中A是栈顶第二个，B是栈顶第一个，C是新推入的），确保合并时两个Run的长度尽可能相近，缩小归并开销。这个启发式保证栈的深度为O(log N)，总合并代价为O(N log N)。

// TimSort 核心简化的伪代码
List<Integer> runs = new ArrayList<>();
int i = 0;
while (i < n) {
    int runLen = detectRun(arr, i); // 识别自然有序段
    if (runLen < MIN_RUN) {
        runLen = MIN_RUN;
        binaryInsertionSort(arr, i, min(i + MIN_RUN, n));
    }
    runs.add(i); runs.add(runLen);
    i += runLen;
    // 维护Run栈平衡
    while (runs.size() >= 3) {
        int x = runs.size() - 3;
        if (runs.get(x) <= runs.get(x+1) + runs.get(x+2) ||
            runs.get(x+1) <= runs.get(x+2)) {
            merge(arr, runs.get(x), runs.get(x), runs.get(x+1), runs.get(x+2));
            // 更新runs列表中的记录
        } else break;
    }
}
// 最终合并所有Run

TimSort的时间复杂度：最好O(N)（数据已有序时），平均和最坏O(N log N)。空间复杂度O(N)（需要临时数组用于合并）。稳定。

八、排序算法的选择指南与实际工程建议

实际工程中排序算法的选择取决于数据特征和约束条件。以下是分场景的推荐：

通用内存排序（Java场景）：

• 原始类型（int, long, double等）：Arrays.sort() 使用 Dual-Pivot QuickSort，因为原始类型不需要稳定性（int的两个”1”完全等价），而快速排序的常数因子最小。
• 对象类型（String, 自定义类等）：Arrays.sort() 和 Collections.sort() 使用 TimSort。对象类型需要稳定性（Comparator比较相等的元素可能有不同的业务含义），而TimSort在部分有序数据上性能极好，实际场景中大部分数据存在天然的部分有序性。

小规模数据（N < 50）：插入排序。简洁、无额外内存、常数极小，在CPU缓存中整个数组可以全部驻留。

几乎有序数据：TimSort 或 插入排序（如果N不大）。TimSort的Run检测和Galloping模式使其在这类数据上接近O(N)。

大规模固定宽度整数：基数排序（8位基数，4轮）。在N > 10^6时，基数排序通常比快速排序快30-100%。但需要额外O(N)内存。

流式数据 / Top K：不需要全量排序。对于Top K使用大小为K的最小堆（O(N log K)）；对于实时中位数维护使用两个堆（O(log N)每次操作）。

多关键字排序：使用稳定排序算法从最低优先级的关键字开始逐层排序（基数排序思想）。例如，先按姓名排序（使用稳定的TimSort），再按成绩排序——最终同分的记录保持姓名字典序。

外排序（磁盘数据）：使用归并排序的外排序版本（多路归并+替换选择算法提高初始Run长度）。

并发排序：Java 8引入的Arrays.parallelSort()使用ForkJoinPool实现的并行归并排序，在数据量大于阈值（通常为8192个元素）时自动启用并行。归并排序天然适合并行化——两个子数组可以独立排序后再合并。

九、复杂度对比总结

算法	最好	平均	最坏	空间	稳定	原地	适应
冒泡排序	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 log N)	~O(N^(4/3))	O(N^(3/2))	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)	是	否	否
基数排序	O(d(N+K))	O(d(N+K))	O(d(N+K))	O(N+K)	是	否	否
TimSort	O(N)	O(N log N)	O(N log N)	O(N)	是	否	是

表中的”适应”指算法是否利用了输入的部分有序性（Adaptivity）。注意计数排序和基数排序虽非原地，但它不是比较排序，不受Ω(N log N)下界约束。

十、面试常见追问

问题一：为什么快速排序在实际中通常比归并排序快？

尽管两者平均复杂度同为O(N log N)，快速排序的常数因子更小（约小2-3倍）。原因如下：（1）快速排序的分区操作是局部的——只在一个连续段内交换元素，内存访问模式是顺序扫描的，缓存命中率极高；（2）归并排序的合并操作需要额外的数组空间，并在两个数组间跳跃读取和写入，缓存局部性差；（3）快速排序是原地的（除了递归栈），而归并排序需要O(N)临时数组的分配和拷贝，内存分配本身也有开销；（4）快速排序的内循环极其紧凑——只需一次比较和偶尔一次交换，而归并排序的合并阶段每次迭代需要多次比较、条件判断和数组拷贝；（5）随机化Pivot选择使得最坏情况的发生概率随N增大呈指数级降低，在实际中可以忽略。

问题二：堆排序的Build-Heap过程为什么是O(N)而不是O(N log N)？

建堆过程从最后一个非叶子节点开始（索引n/2-1）依次向上执行下沉操作。关键洞察是：不同高度的节点数量呈指数分布——大约N/2个叶子节点（高度0，不下沉），N/4个节点高度为1（最多下沉1层），N/8个节点高度为2（最多下沉2层），以此类推。设满二叉堆的高度h = ⌊log₂N⌋，总下沉次数 ≤ Σ(k=0→h) k × N/2^(k+1) < N × Σ(k=0→∞) k/2^(k+1)。级数Σ k/2^(k+1) = 1（可通过生成函数求得），因此总和 < N = O(N)。直观上：”下沉深度”被”节点数量”的指数衰减所抵消，使得建堆的均摊代价仅为常数级别。

问题三：如何在O(N)时间内找到第K大的元素？

使用快速选择算法（QuickSelect），它是快速排序的变体。每次分区后，根据Pivot位置p与K的关系决定下一步：如果p == K，找到目标；如果p < K，只在右半区递归；如果p > K，只在左半区递归。与快速排序不同，QuickSelect每次只递归一边，因此期望时间复杂度为O(N)（N + N/2 + N/4 + … = O(N)）。随机化Pivot保证期望线性时间。需要注意QuickSelect不是原地操作（虽然可以用迭代实现避免递归栈），并且它天然是不稳定的。实际中，当K较小（如K ≤ 100）时，建大小为K的最小堆并遍历数组（O(N log K)）可能比QuickSelect更快，因为K log K的常数小，且不需要修改原数组。

问题四：TimSort为什么选择MIN_RUN = 32？

MIN_RUN的选择是一个精确的性能权衡。如果MIN_RUN太小，Run的数量增多（接近N/MIN_RUN个Run），归并次数增多（每次合并都需要临时数组和拷贝），合并开销增加。如果MIN_RUN太大，二分插入排序退化为O(N²)的成分增加（插入排序对小数组O(N²)但在极小数组上常数极小）。32是实验得到的最优值——在这个大小上，插入排序的O(N²)系数（约N²/4次比较）在32²/4=256次比较，仍在CPU可瞬时完成的量级，同时Run数量被控制在N/32，归并开销可控。对于特定硬件（不同的缓存大小和分支预测能力），最优值在16到64之间变化。Java的实现会根据数组大小动态计算MIN_RUN（n < 64时直接用插入排序）。

问题五：为什么基数排序很少作为通用排序的默认选择？

尽管基数排序在特定条件下（固定宽度的整数，N很大时）比快速排序快，但它有显著局限：（1）需要额外的O(N)内存（输出数组），在内存受限场景下不可接受；（2）只适用于可逐位解析的键（整数、定长字符串），对浮点数（IEEE 754二进制表示需要特殊处理以保持排序顺序）、变长字符串、自定义对象等不友好；（3）性能高度依赖于基数的选择和计数数组能否放入缓存——换一种数据类型或硬件，最优参数可能完全不同；（4）不能同时提供稳定性、原地性和适应性。而快速排序/TimSort是通用的稳定方案，可以处理任何可比较的对象类型，无需了解数据的内部表示。

问题六：如何对大规模数据（超出内存）进行排序？

外排序（External Sort）的标准流程分为两个阶段。第一阶段（Run Generation）：将数据分块读入内存（每块大小等于可用内存），每块在内存中使用高效排序算法（如快速排序）排序后，作为一个”归并段”（Run）写回磁盘。为了提高初始Run的长度，可使用替换选择算法（Replacement Selection）——维护一个最小堆，每次输出堆顶元素（最小值）到Run文件，然后读入下一个输入元素；如果新元素大于等于刚输出的元素，加入堆继续；如果新元素小于刚输出的元素，将其标记为”冻结”（放入下一轮）。这样生成的Run长度平均为2M（M为可用内存可容纳的元素数），而非标准的M。

第二阶段（Multi-way Merge）：使用K路归并将多个有序Run合并为最终输出。维护一个大小为K的最小堆（或败者树），每个Run对应一个输入缓冲区。每次从堆中取出最小值输出，然后从对应Run的缓冲区中补充下一个元素。K的选择受限于文件描述符数量和缓冲区内存：K过小则归并趟数增多（总趟数 = ⌈log_K(R)⌉，R为Run数量）；K过大则每个Run的缓冲区太小，I/O效率下降。实际中，K通常在数十到数百之间。

现代数据库系统（如PostgreSQL、MySQL）的ORDER BY和CREATE INDEX操作，当排序数据超过work_mem或sort_buffer_size时，自动启用外排序。PostgreSQL使用基于tape的外排序，结合logtape管理临时文件；MySQL使用归并排序+优先队列。

问题七：排序算法的并行化策略有哪些？

并行排序的主流方法：（1）并行归并排序——将数组均分为P份（P为处理器数），每个处理器独立排序一份，然后使用P路并行归并（如使用双调归并网络，Bitonic Merge）。Java 8的Arrays.parallelSort()使用ForkJoinPool实现此策略。（2）并行快速排序——在分区后，对左右两个分区分别提交到线程池中并行排序。需要注意任务粒度——当子数组小于某个阈值（如8192）时切换回顺序排序，避免线程调度开销超过排序本身。（3）样本排序（Sample Sort）——从数据中采样P-1个分隔元素（Splitters），将数据分到P个桶中（每个处理器处理一个桶），桶内排序后直接按顺序拼接（无需归并，因为桶之间已通过分隔元素保证全局有序）。样本排序的关键是选取好的分隔元素（通常随机采样+排序后取分位点）以保证各桶大小均衡。在GPU排序中，基数排序（利用GPU的并行前缀和/scan操作）常常是最快的方法。

十一、排序算法的缓存效率与分支预测分析

排序性能的工程优化与两个硬件特性密切相关。

缓存效率（Cache Efficiency）：现代CPU的L1缓存约32KB，L2约256KB，L3约8-32MB。排序算法访问内存的模式决定了缓存命中率。快速排序分区时顺序扫描数组，预取（Prefetching）机制可提前将数据加载到缓存，每访问一个元素就是下一个缓存行的开始。归并排序合并时需要交替从两个子数组读取，缓存抖动较大（尤其当两个子数组大小相近时）。堆排序的siftDown操作在父子节点间跳跃（索引i → 2i+1 → 4i+3…），每层访问可能触发新的缓存miss，对大数据集尤其不利。插入排序在小数据集（N<50）上全部在L1缓存中完成，极快。TimSort通过识别Run和Galloping模式减少了归并时的缓存抖动。

分支预测（Branch Prediction）：现代CPU使用分支预测器猜测条件跳转的方向。排序算法的内循环中通常包含分支（如”if a[j] < pivot”）。对于随机数据，分支大约50%可预测（接近随机猜测，导致大量分支预测错误，每次错误惩罚约15-20个时钟周期）。分支预测错误是快速排序内循环性能的主要制约因素之一。解决策略：（1）无条件移动（cmov指令）——使用条件移动指令替代分支跳转。GCC/Clang在优化级别O2以上会将某些简单分支优化为cmov。（2）排序网络（Sorting Network）——对小规模排序（N<16）使用硬编码的无分支比较交换序列（如Batcher奇偶归并网络），完全消除分支。（3）SIMD向量化——使用SSE/AVX指令同时比较多个元素。

真实基准测试数据（来自标准benchmark，排序10^7个随机int）：

• std::sort（内省排序，Introsort）：约0.35秒
• absl::flat_hash_map无意义（跳过）
• C qsort（函数指针回调）：约1.2秒（函数调用开销巨大）
• 手写Dual-Pivot QuickSort：约0.30秒
• LSD基数排序（8位基数）：约0.15秒
• Java Arrays.sort(int[])（Dual-Pivot）：约0.40秒（含JVM开销）

注意C的qsort由于每次比较都需要通过函数指针回调，比内联比较的C++ std::sort慢3-4倍。这也是Java使用接口Comparable比C的qsort高效的原因——JIT可以将Comparable调用内联化。

十二、面试常见追问补充

问题八：如何对10GB的文件按行排序，内存只有1GB？

标准外排序流程：（1）将10GB文件划分为10个1GB的块，每块读入内存，使用快速排序/TimSort排序后写回磁盘（形成10个有序Run）。（2）使用K路归并（K可根据内存大小选择，如K=10）。为每个Run分配一个输入缓冲区（如10MB），所有缓冲区共享剩余的900MB内存。（3）使用最小堆（大小为K=10）进行K路归并：初始从每个Run的缓冲区读第一个元素放入堆。重复从堆顶取最小值输出，然后从相应Run的缓冲区补充下一个元素。（4）当某Run的缓冲区耗尽时，从磁盘补充该Run的下一段数据。（5）当内存充裕时可以使用替换选择算法生成更长的初始Run（比1GB更长的有序段），减少归并趟数。对于10GB数据，1GB内存，标准做法约2趟即可完成。

问题九：浮点数如何排序？基数排序可以排序浮点数吗？

IEEE 754双精度浮点数的位表示有一个精妙特性：对于非负数，其整数位表示的大小关系与浮点数值的大小关系完全一致（因为指数在高位且使用偏移编码）。对于负数，其整数位表示的序关系与浮点数值相反（负数使用补码表示，绝对值越大整数值越大但浮点值越小）。因此要对浮点数进行基数排序，可以：先将所有浮点数的位模式当作整数读取；对于非负数，翻转符号位（0→1）；对于负数，翻转所有位。转换后的整数保持了与原始浮点数相同的排序顺序。具体实现：

// float转成可基数排序的int
int sortableFloatBits(float f) {
    int bits = Float.floatToIntBits(f);
    if ((bits & 0x80000000) != 0) {
        return ~bits; // 负数：翻转所有位
    } else {
        return bits ^ 0x80000000; // 非负数：翻转符号位
    }
}