快速排序

📖 算法简介

快速排序是一种高效的排序算法，由英国计算机科学家托尼·霍尔在1960年开发。它使用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

核心思想：选择一个基准元素，将数组分为两部分，左边都小于基准，右边都大于基准，然后递归处理左右两部分。

🔍 算法原理

基本步骤

1. 选择基准（Pivot）：从数组中选择一个元素作为基准
2. 分区（Partition）：重新排列数组，使得：
   • 所有小于基准的元素都在基准左边
   • 所有大于基准的元素都在基准右边
3. 递归排序：递归地对基准左边和右边的子数组进行快速排序

算法流程图

初始数组: [3, 6, 8, 10, 1, 2, 1]
选择基准: 3

分区后: [1, 2, 1] + [3] + [6, 8, 10]
         ↓              ↓
    递归排序左边    递归排序右边

最终结果: [1, 1, 2, 3, 6, 8, 10]

⏱️ 复杂度分析

时间复杂度

• 最好情况：O(n log n) - 每次分区都能将数组平均分成两部分
• 平均情况：O(n log n) - 随机选择基准的期望性能
• 最坏情况：O(n²) - 每次选择的基准都是最大或最小元素

空间复杂度

• 平均情况：O(log n) - 递归调用栈的深度
• 最坏情况：O(n) - 退化为链式递归

💻 代码实现

Java 实现

public class QuickSort {
    
    /**
     * 快速排序主方法
     * @param arr 待排序数组
     * @param low 起始索引
     * @param high 结束索引
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(arr, low, high);
            
            // 递归排序左半部分
            quickSort(arr, low, pivotIndex - 1);
            
            // 递归排序右半部分
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    /**
     * 分区方法（Lomuto分区方案）
     * @param arr 数组
     * @param low 起始索引
     * @param high 结束索引
     * @return 基准元素的最终位置
     */
    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++;
                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 = {3, 6, 8, 10, 1, 2, 1};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        quickSort(arr, 0, arr.length - 1);
        
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

Python 实现

def quick_sort(arr, low=0, high=None):
    """
    快速排序主函数
    :param arr: 待排序列表
    :param low: 起始索引
    :param high: 结束索引
    """
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # 获取分区点
        pivot_index = partition(arr, low, high)
        
        # 递归排序左右两部分
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    分区函数
    :param arr: 数组
    :param low: 起始索引
    :param high: 结束索引
    :return: 基准元素的最终位置
    """
    # 选择最后一个元素作为基准
    pivot = arr[high]
    
    # 小于基准的元素的索引
    i = low - 1
    
    for j in range(low, high):
        # 如果当前元素小于或等于基准
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准放到正确位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 测试代码
if __name__ == "__main__":
    test_arr = [3, 6, 8, 10, 1, 2, 1]
    print(f"排序前: {test_arr}")
    
    quick_sort(test_arr)
    
    print(f"排序后: {test_arr}")

🚀 算法优化

1. 三数取中法选择基准

private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (arr[mid] < arr[low]) {
        swap(arr, low, mid);
    }
    if (arr[high] < arr[low]) {
        swap(arr, low, high);
    }
    if (arr[high] < arr[mid]) {
        swap(arr, mid, high);
    }
    
    // 将中位数放到末尾作为基准
    swap(arr, mid, high);
    return high;
}

2. 小数组使用插入排序

public static void optimizedQuickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 当子数组长度小于10时，使用插入排序
        if (high - low < 10) {
            insertionSort(arr, low, high);
        } else {
            int pivotIndex = partition(arr, low, high);
            optimizedQuickSort(arr, low, pivotIndex - 1);
            optimizedQuickSort(arr, pivotIndex + 1, high);
        }
    }
}

3. 三路快排（处理重复元素）

public static void threeWayQuickSort(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 + 1; // arr[gt...high] > pivot
    int i = low + 1;   // 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++;
        }
    }
    
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt, high);
}

📊 性能比较

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定

🎯 应用场景

适用场景

• 大数据量的内存排序
• 对平均性能要求高的场景
• 不需要稳定排序的情况
• 系统库实现（如Java的Arrays.sort()）

不适用场景

• 需要稳定排序的场景
• 最坏情况性能不能接受O(n²)的场景
• 栈空间受限的环境

🤔 常见面试题

1. 快速排序的时间复杂度为什么是O(n log n)？

答案：在平均情况下，每次分区操作需要O(n)时间，而递归深度为O(log n)，所以总时间复杂度为O(n log n)。

2. 如何避免快速排序的最坏情况？

答案：

• 使用随机化选择基准
• 采用三数取中法选择基准
• 使用三路快排处理大量重复元素

3. 快速排序是稳定排序吗？

答案：不是。快速排序在分区过程中会改变相等元素的相对位置。

4. 快速排序的空间复杂度是多少？

答案：平均情况下为O(log n)（递归栈深度），最坏情况下为O(n)。

📝 总结

快速排序是一种高效的排序算法，具有以下特点：

优点：

• 平均性能优秀，时间复杂度为O(n log n)
• 原地排序，空间复杂度低
• 实际应用中性能很好
• 可以通过各种优化技巧进一步提升性能

缺点：

• 最坏情况时间复杂度为O(n²)
• 不是稳定排序
• 递归实现可能导致栈溢出

学习要点：

1. 理解分治思想的应用
2. 掌握分区操作的实现
3. 了解各种优化技巧
4. 能够分析时间和空间复杂度
5. 知道适用场景和局限性

快速排序是面试和实际开发中都非常重要的算法，值得深入学习和掌握。