快速排序：分治思想的经典实践

排序算法是计算机科学的基石，而快速排序以其卓越的性能和优雅的实现，成为最广泛应用的排序算法之一。本文将深入剖析快速排序的每个细节，带大家领略这一经典算法的魅力。

前言

在计算机科学中，排序算法是最基础也是最重要的算法之一。快速排序由英国计算机科学家Tony Hoare于1959年发明，凭借其平均情况下O(n log n)的出色性能和简洁的实现，成为众多编程语言标准库中的首选排序算法。本文将从核心思想到具体实现，全面解析快速排序的工作原理。

🌟 核心思想

快速排序采用分治策略：

1. 选择基准：从数组中选取一个元素作为"基准"，这也是和归并排序分治思想的区别。
2. 分区操作：将数组分为两部分，使得：
   • 所有小于基准的元素位于基准左侧。
   • 所有大于基准的元素位于基准右侧。
   • 基准元素位于最终正确位置。
3. 递归排序：对左右两个子数组递归应用相同过程。

分区操作是快速排序的核心，它确保了每次递归调用都能将一个元素（基准）放置到其最终位置。

⚙️ Java实现

public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        sort(arr, 0, arr.length - 1);
    }

    private 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;  // 指向小于基准的子数组的末尾
        
        for (int j = low; j < high; j++) {
            // 当前元素小于或等于基准
            if (arr[j] <= pivot) {
                i++;
                // 交换arr[i]和arr[j]
                swap(arr, i, j);
            }
        }
        
        // 将基准元素放到正确位置
        swap(arr, i + 1, high);
        return i + 1;  // 返回基准索引
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr));
    }
}

代码解析：

1. quickSort()是入口方法，处理边界情况。
2. sort()方法实现递归排序逻辑。
3. partition()是关键方法，完成分区操作：
   • 选择最右侧元素作为基准（pivot）
   • 使用双指针技巧（i和j）进行分区
   • 最终将基准放到正确位置
4. swap()辅助方法用于交换数组元素。

🔍 时间复杂度分析

快速排序的时间复杂度取决于分区操作的平衡性：

最坏情况分析：当输入数组已经有序时，每次分区只能减少一个元素（基准），导致递归树深度为n，每层需要O(n)时间，总时间为O(n²)。

📦 空间复杂度

快速排序是原地排序算法，但递归调用需要栈空间：

• 最佳/平均：O(log n)（平衡的递归树深度）。
• 最坏：O(n)（退化的递归树）。

✅ 算法特性

1. 不稳定排序：相等元素的相对顺序可能改变。
2. 原地排序：只需要O(1)的额外空间（递归栈除外）。
3. 分治策略：将大问题分解为小问题解决。
4. 实用高效：实际应用中通常比其他O(n log n)算法更快。

⚡ 优化技巧

此模块先简单说一下常见的优化方法，下一篇我们深入探讨

1. 随机选择基准：避免最坏情况发生。

private static int randomizedPartition(int[] arr, int low, int high) {
    int randomIndex = low + (int)(Math.random() * (high - low + 1));
    swap(arr, randomIndex, high);
    return partition(arr, low, high);
}

2. 三数取中法：选择首、中、尾三元素的中值作为基准。

private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low)/2;
    // 找到首、中、尾的中值
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    return mid;
}

3. 小数组使用插入排序：当子数组规模较小时（如长度<15，局部有序的概率高），切换为插入排序。（这里具体为什么建议小于15时改为插入排序，上一篇递归排序有详细说明，这里同样的道理，这里不在多说）。

private static final int INSERTION_THRESHOLD = 10;

private static void sort(int[] arr, int low, int high) {
    if (high - low < INSERTION_THRESHOLD) {
        insertionSort(arr, low, high);
        return;
    }
    // 快速排序逻辑...
}

4. 尾递归优化：减少递归深度。

private static void tailRecursiveSort(int[] arr, int low, int high) {
    while (low < high) {
        int pivotIndex = partition(arr, low, high);
        if (pivotIndex - low < high - pivotIndex) {
            tailRecursiveSort(arr, low, pivotIndex - 1);
            low = pivotIndex + 1;
        } else {
            tailRecursiveSort(arr, pivotIndex + 1, high);
            high = pivotIndex - 1;
        }
    }
}

5. 双轴快排：Java标准库Arrays.sort()采用的方法，使用两个基准值进行分区。

💡 实际应用场景

快速排序因其高效性被广泛应用于：

1. 编程语言标准库（如Java的Arrays.sort()）。
2. 数据库索引构建和查询优化。
3. 大数据处理框架中的排序阶段。
4. 需要高效排序的各类应用程序。

🌐 总结

快速排序是分治思想的完美体现，其核心在于高效的分区操作：

• 优势：平均情况下O(n log n)的时间复杂度，原地排序，实现简单。
• 劣势：最坏情况O(n²)时间复杂度，不稳定排序。
• 适用场景：大规模随机数据排序。
• 优化关键：合理选择基准，避免最坏情况。

通过随机选择基准、三数取中等优化策略，可以显著降低最坏情况发生的概率。在实际应用中，快速排序通常比其他O(n log n)的排序算法（如归并排序、堆排序）更快，因为它的常数因子更小，对缓存更友好。