第2章：排序（Sorting）

一、导读

1.1 本章学习目标

第2章系统介绍各种排序算法，这是算法学习的基础。排序看似简单，但其中蕴含了丰富的算法设计思想。本章的核心学习目标包括：

掌握基本排序算法：选择排序、插入排序的原理和实现
理解希尔排序的改进思路：如何突破O(n²)的限制？
深入理解分治思想：归并排序和快速排序如何应用分治策略？
掌握堆排序：如何利用堆数据结构实现排序？
学会分析排序算法的性能：时间复杂度、空间复杂度、稳定性
了解Java的排序实现：Arrays.sort()内部使用了什么算法？

1.2 为什么本章如此重要

排序是计算机科学中最基础也是最重要的问题之一。Donald Knuth曾估计，在20世纪70年代，超过25%的计算时间花在排序上。虽然现代硬件快了很多，但排序算法的设计思想——分治、贪心、数据结构的巧妙运用——仍然是算法学习的核心。

1.3 核心问题引导

为什么排序算法的下界是O(n log n)？有没有例外？

插入排序在什么情况下比快速排序更快？

归并排序和快速排序都使用分治，为什么快排通常更快？

什么是排序的稳定性？为什么它很重要？

堆排序的时间复杂度是O(n log n)，为什么实际中不如快排？

Java的Arrays.sort()为什么对不同数据类型使用不同算法？

二、核心概念详解

2.1 排序算法概览

算法	最好	平均	最坏	空间	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	否
插入排序	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)	否

2.2 选择排序

选择排序的思路很简单：每次从未排序部分找到最小元素，放到已排序部分的末尾。

java

public class Selection {
    public static void sort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[min]) min = j;
            }
            swap(a, i, min);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

分析：无论输入如何，选择排序总是需要约n²/2次比较和n次交换。它的时间复杂度始终是O(n²)，且不稳定。

2.3 插入排序

插入排序模拟了整理扑克牌的过程：将每个元素插入到前面已排序序列的正确位置。

java

public class Insertion {
    public static void sort(int[] a) {
        int n = a.length;
        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;
        }
    }
}

分析：

最好情况（已排序）：O(n)，只需n-1次比较，0次交换
最坏情况（逆序）：O(n²)
平均情况：O(n²)
稳定：相等元素的相对顺序不变
优势：对于小规模或部分有序的数组非常快

2.4 希尔排序

希尔排序是插入排序的改进版，通过允许不相邻的元素交换来加速排序：

java

public class Shell {
    public static void sort(int[] a) {
        int n = a.length;
        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 = a[i];
                int j = i;
                while (j >= h && a[j - h] > key) {
                    a[j] = a[j - h];
                    j -= h;
                }
                a[j] = key;
            }
            h /= 3;
        }
    }
}

分析：希尔排序的时间复杂度取决于增量序列的选择。使用 Hibbard 增量序列（1, 3, 7, 15, ...）时，最坏情况为 O(n¹·⁵)。

2.5 归并排序

归并排序是分治思想的经典应用：将数组分成两半，分别排序，然后合并。

java

public class Merge {
    private static int[] aux;
    
    public static void sort(int[] a) {
        aux = new int[a.length];
        sort(a, 0, a.length - 1);
    }
    
    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
    
    private static void merge(int[] a, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
}

分析：

时间复杂度：始终O(n log n)
空间复杂度：O(n)，需要辅助数组
稳定
递推关系：T(n) = 2T(n/2) + O(n)，解为T(n) = O(n log n)

2.6 快速排序

快速排序是实际应用最广泛的排序算法，也使用分治策略：

java

public class Quick {
    public static void sort(int[] a) {
        shuffle(a);  // 随机化，避免最坏情况
        sort(a, 0, a.length - 1);
    }
    
    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
    
    private static int partition(int[] a, int lo, int hi) {
        int pivot = a[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (a[++i] < pivot) if (i == hi) break;
            while (a[--j] > pivot) if (j == lo) break;
            if (i >= j) break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }
    
    private static void shuffle(int[] a) {
        java.util.Random rnd = new java.util.Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = rnd.nextInt(i + 1);
            swap(a, i, j);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

分析：

平均时间复杂度：O(n log n)
最坏时间复杂度：O(n²)（已排序数组+固定选第一个为pivot）
空间复杂度：O(log n)（递归栈）
不稳定
实际中通常比归并排序快2-3倍，因为内部循环更紧凑

2.7 堆排序

堆排序利用堆（完全二叉树）的性质进行排序：

java

public class Heap {
    public static void sort(int[] a) {
        int n = a.length;
        // 建堆（从最后一个非叶节点开始下沉）
        for (int k = n / 2; k >= 1; k--)
            sink(a, k, n);
        // 排序（将最大值交换到末尾）
        while (n > 1) {
            swap(a, 1, n);
            n--;
            sink(a, 1, n);
        }
    }
    
    private static void sink(int[] a, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && a[j - 1] < a[j]) j++;
            if (a[k - 1] >= a[j - 1]) break;
            swap(a, k - 1, j - 1);
            k = j;
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

分析：

时间复杂度：始终O(n log n)
空间复杂度：O(1)
不稳定
实际中不如快排，因为缓存不友好

三、实战案例

3.1 排序算法性能对比

java

import java.util.Arrays;
import java.util.Random;

public class SortComparison {
    public static void main(String[] args) {
        int n = 10000;
        int[] original = new int[n];
        Random rnd = new Random();
        for (int i = 0; i < n; i++)
            original[i] = rnd.nextInt(n);
        
        // 测试各算法
        int[] a = original.clone();
        long start = System.nanoTime();
        Insertion.sort(a);
        long time = System.nanoTime() - start;
        System.out.printf("Insertion: %.3f ms%n", time / 1e6);
        
        a = original.clone();
        start = System.nanoTime();
        Merge.sort(a);
        time = System.nanoTime() - start;
        System.out.printf("Merge: %.3f ms%n", time / 1e6);
        
        a = original.clone();
        start = System.nanoTime();
        Quick.sort(a);
        time = System.nanoTime() - start;
        System.out.printf("Quick: %.3f ms%n", time / 1e6);
        
        a = original.clone();
        start = System.nanoTime();
        Arrays.sort(a);
        time = System.nanoTime() - start;
        System.out.printf("Arrays.sort: %.3f ms%n", time / 1e6);
    }
}

3.2 小规模数组使用插入排序的优化快排

java

public class OptimizedQuick {
    private static final int INSERTION_THRESHOLD = 15;
    
    public static void sort(int[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }
    
    private static void sort(int[] a, int lo, int hi) {
        if (hi - lo <= INSERTION_THRESHOLD) {
            Insertion.sort(a, lo, hi);
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
    
    // partition和shuffle同上
}

四、本章小结

第2章系统介绍了排序算法：

O(n²)算法：选择排序、插入排序简单但低效。插入排序对小规模或部分有序数据很快。

希尔排序：通过允许不相邻元素交换突破O(n²)。

归并排序：分治思想，始终O(n log n)，稳定，但需要O(n)额外空间。

快速排序：实际应用最广，平均O(n log n)，内部循环紧凑，但不稳定。

堆排序：O(n log n)且O(1)空间，但缓存不友好。

五、思考与练习

思考题

为什么比较排序的下界是Ω(n log n)？非比较排序能突破这个限制吗？

快速排序为什么比归并排序在实际中更快？

什么是三向切分快速排序？它在什么场景下特别有效？

为什么Java的Arrays.sort()对基本类型使用双轴快排，对对象使用TimSort？

如何验证一个排序算法是否稳定？

编程练习

实现归并排序的自底向上版本（不使用递归）。

实现三向切分快速排序，处理大量重复元素的情况。

编写程序实测各排序算法在不同输入（随机、有序、逆序、大量重复）下的性能。