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

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

排序是计算机科学中最基础的操作之一。根据数据是否全部加载到内存，排序算法分为内排序（所有数据在内存中完成排序）和外排序（数据量太大，需要借助外部存储）。本文聚焦于内排序的经典算法。

评价一个排序算法主要有三个维度。时间复杂度：最好、最坏和平均情况下的比较和移动次数。空间复杂度：除输入数据外所需的额外内存——原地排序（In-Place）算法的空间复杂度为O(1)。稳定性：排序后相等元素的相对顺序是否保持不变。稳定性在多关键字排序中至关重要——例如先按成绩排序，再按姓名排序（同分的人内部仍保持姓名的字典序）。

排序算法的下界：基于比较的排序算法在最坏情况下至少需要Ω(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)。归并排序和堆排序在最坏情况下达到了这个理论下界，是最优的比较排序算法。

二、快速排序

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

快速排序的核心是分区（Partition）算法。以Lomuto分区方案为例：

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;
    }
}

快速排序的平均时间复杂度为O(N log N)，最坏情况为O(N²)——当数组已经有序（或逆序）且每次选最左或最右元素为Pivot时，分区极不平衡，退化为冒泡排序。解决方案是随机化Pivot选择——在分区前，随机选择数组中的一个元素与最右元素交换，使得最坏情况的发生概率指数级降低。数学上可以证明，随机化快速排序的期望时间复杂度为O(N log N)。

另一种改进是Hoare分区方案，它比Lomuto方案的交换次数更少（平均约少3倍），但实现略复杂。Java的Arrays.sort()对原始类型使用Dual-Pivot QuickSort，选择两个Pivot将数组划分为三段，进一步提升了性能。

快速排序是不稳定的——分区过程中的交换会打乱相等元素的相对顺序。空间复杂度为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)，递归深度为O(log N)。归并排序是稳定的，因为在合并时当左右元素相等时，优先取左边的元素，保持了原始顺序。空间复杂度为O(N)（需要临时数组），这是归并排序相比快速排序的主要劣势。

归并排序非常适合外排序场景。当数据量超出内存容量时，可以将数据分块读入内存排序后写回磁盘（形成多个有序的“归并段”），然后使用多路归并通过堆选择最小元素，逐步输出最终排序结果。数据库的ORDER BY在数据量大于sort_buffer_size时的排序操作，使用的就是基于归并排序的外排序。

四、堆排序

堆排序（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) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < heapSize && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < heapSize && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest == i) break;
            swap(arr, i, largest);
            i = largest;
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

堆排序的时间复杂度在所有情况下都是O(N log N)。Build-Heap的过程看似是O(N log N)（N个元素各下沉一次），但精细分析表明它是O(N)——不同高度的节点数量不同，下沉的深度也不同，求和后得到线性时间。详细分析：对于一个满二叉堆，高度为h的节点最多有⌈N / 2^(h+1)⌉个，每个最多下沉h层。总下沉次数为Σ(h × N/2^(h+1)) = O(N)。这个证明在面试中是加分项。

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

五、线性时间排序算法

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

计数排序（Counting Sort）：适用于取值范围较小的整数。统计每个值出现的次数，然后计算累积分布，最后直接将元素放到正确位置。时间复杂度O(N + K)，K为取值范围大小。空间复杂度O(K)。稳定。

public static void countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    for (int v : arr) count[v]++;
    int idx = 0;
    for (int v = 0; v <= maxVal; v++) {
        while (count[v]-- > 0) arr[idx++] = v;
    }
}

基数排序（Radix Sort）：从最低位（LSD）或最高位（MSD）开始，逐位使用稳定的排序算法（通常是计数排序，因为每位取值范围为0到9）。时间复杂度O(d × (N + K))，其中d为数字的位数。空间复杂度O(N + K)。基数排序在对固定宽度的整数（如32位整数）排序时，每8位一组，只需要4轮计数排序，实际性能可以接近甚至超过快速排序。

桶排序（Bucket Sort）：将数据均匀分布到若干个桶中，每个桶内使用其他排序算法（如插入排序）排序，然后按桶的顺序合并。如果桶的数量与元素数量相近且数据均匀分布，平均时间复杂度为O(N)。最坏情况（所有元素落到同一个桶中）退化为桶内排序算法的复杂度。

六、排序算法的选择指南

实际工程中排序算法的选择取决于数据特征和约束条件：

对于内存中的普通数组排序，Java的Arrays.sort()对原始类型（int、long等）使用双轴快速排序（Dual-Pivot QuickSort），对对象类型（Object）使用TimSort（一种自适应归并排序变体）。这是因为原始类型不需要稳定性（int的1和1没有区别），而快速排序的常数因子更小；对象类型需要考虑稳定性（Comparator比较相等的元素可能仍有不同的业务含义），TimSort在部分有序的数据上性能极好。

TimSort是Python和Java使用的排序算法，它结合了归并排序和插入排序的思想。TimSort识别输入中自然存在的有序段（Run），对短Run使用二分插入排序扩张，然后使用归并排序合并这些Run。在部分有序的数据上，TimSort可以达到O(N)的时间复杂度。Java的Collections.sort()和Arrays.sort(Object[])使用的就是TimSort。

对于键值对按Key排序的场景，如果数据量大且Key范围有限，基数排序是很好的选择。对于Top K问题（找出最大的K个元素），堆排序优于全量排序。对于流式数据（不断有新数据加入），可以使用堆维护Top K，或者使用红黑树（TreeMap）维护全量有序数据。

七、复杂度对比总结

算法	最好	平均	最坏	空间	稳定	原地
冒泡排序	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 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)	是	否

八、面试常见追问

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

尽管两者平均复杂度同为O(N log N)，快速排序的常数因子更小。原因在于：快速排序的分区操作是局部的（只在一个连续段内交换元素），缓存局部性极好；而归并排序的合并操作需要额外的数组空间，并在两个数组间跳跃读取。快速排序是原地的（除了递归栈），而归并排序需要O(N)的临时数组。此外，快速排序的内循环非常紧凑——只需比较和偶尔交换，而归并排序的合并需要更多的条件判断和数组拷贝。在随机化Pivot选择后，快速排序的最坏情况几乎不可能出现。

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

考虑一个高度为h的满二叉堆。第0层（根）有1个节点，下沉h层；第1层有2个节点，下沉h-1层；…；第h-1层有2^(h-1)个节点，下沉1层；第h层（叶子）有2^h个节点，下沉0层。总下沉次数为Σ(i从0到h) (h-i) × 2^i。求和结果为2^(h+1) - h - 2。由于N = 2^(h+1) - 1，总和约为N - log N = O(N)。直观理解：绝大多数节点在下层（靠近叶子），它们的下沉距离很短；只有极少数上层节点需要长距离下沉。

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

使用快速选择算法（QuickSelect），它是快速排序的变体。每次分区后，根据Pivot的位置与K的关系，只递归进入一边（包含第K大元素的那一边），另一边的数据直接丢弃。平均时间复杂度为O(N)（N + N/2 + N/4 + … = 2N），最坏情况O(N²)。随机化Pivot选择保证了期望O(N)的性能。Java的Arrays.sort不直接支持第K大，但可以通过PriorityQueue在O(N log K)时间内解决。如果K较小（如K=10），建一个大小为K的最小堆，遍历数组，比堆顶大则替换并调整，复杂度O(N log K)在实践中优于QuickSelect的递归开销。