快速排序

算法定义

快速排序（Quick Sort）是一种高效的分治法排序算法，由计算机 Tony Hoare 在 1960 年提出。它通过选择一个 "基准值"（pivot），将数组分为两部分，一部分所有元素小于基准值，另一部分所有元素大于基准值，然后递归地对这两部分进行排序。

算法思路

选择基准值：从数组中选择一个元素作为 "基准"（pivot）
分区操作：将所有比基准值小的元素移到基准值前面，所有比基准值大的元素移到基准值后面（相等的元素可以放到任意一边）
递归排序：递归地将小于基准值的子数组和大于基准值的子数组进行排序

这个过程可以概括为 "分而治之"（Divide and Conquer）的策略。

如果问题规模小于100，就把递归换成插入排序

算法复杂度

最好时间复杂度：O (n log n) - 每次划分都将数组分为大致相等的两部分
最坏时间复杂度：O (n²) - 当数组已经有序或逆序，且每次选择最左 / 右端点作为基准值时
平均时间复杂度：O(n log n)
空间复杂度：O (log n) ~ O (n) - 主要来自递归调用栈，取决于递归深度

优点与缺点

优点：
- 平均性能优异，时间复杂度为 O (n log n)
- 原地排序，不需要额外的存储空间
- 缓存友好，局部性好
- 可以并行化处理
缺点：
- 不稳定的排序算法（相等元素的相对位置可能改变）
- 最坏情况下时间复杂度为 O (n²)
- 对于小规模数据，可能不如插入排序高效
- 对基准值的选择敏感

应用场景

大规模数据排序（效率高）
内存有限的场景（原地排序特性）
各种编程语言的标准库实现（如 Java 的Arrays.sort()对原始类型的排序）
需要平均时间复杂度为 O (n log n) 的场景

各版本优化说明

基本版：以最左元素为基准值，实现简单但在有序数组上表现差
随机选择基准值：
- 随机选择数组中的一个元素作为基准值
- 避免了在有序数组上的最坏情况
- 使算法的时间复杂度更加稳定
三数取中法：
- 选择首、中、尾三个位置元素的中间值作为基准
- 进一步优化基准值选择，减少最坏情况发生的概率
- 对于部分有序的数组效果显著
三向切分：
- 将数组分为三部分：小于、等于和大于基准值
- 特别适合处理包含大量重复元素的数组
- 减少了重复元素的比较和交换次数
混合插入排序：
- 当子数组规模小于某个阈值（通常 10-20）时，使用插入排序
- 利用插入排序在小规模数据上的优势
- 减少递归调用次数和函数调用开销

快速排序是实践中最快的排序算法之一，其性能优势在大规模数据排序中尤为明显。通过合适的优化策略，可以使其在各种场景下都保持高效稳定的表现。

双边扫描

在快速排序的分区操作中，单边扫描和双边扫描是两种常见的实现方式，用于将数组划分为元素围绕基准值（pivot）进行划分。它们的核心目标相同 —— 将小于基准值的元素放左边，大于基准值的元素放右边，但实现思路和操作过程不同。

双边扫描（Two-way Partitioning）是最经典的分区方式，从数组的两端向中间同时扫描并交换元素，具体步骤如下：

选择基准值：通常选择数组左端（或右端）的元素作为基准值（pivot）。
初始化指针：左指针low指向数组起始位置，右指针high指向数组末尾。
右指针左移：从右向左扫描，找到第一个小于基准值的元素，停止移动。
左指针右移：从左向右扫描，找到第一个大于基准值的元素，停止移动。
交换元素：交换左右指针指向的元素。
重复操作：直到左指针low >= 右指针high，此时将基准值放到low（或high）的位置，完成分区。

代码示例（双边扫描）：

private static int partitionTwoWay(int[] arr, int low, int high) {
    int pivot = arr[low]; // 选择最左元素为基准值
    int left = low;       // 左指针
    int right = high;     // 右指针
    
    while (left < right) {
        // 右指针左移：找到第一个小于pivot的元素
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        // 左指针右移：找到第一个大于pivot的元素
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换左右指针指向的元素
        if (left < right) {
            swap(arr, left, right);
        }
    }
    // 将基准值放到最终位置（左右指针相遇点）
    swap(arr, low, left);
    return left; // 返回基准值索引
}

特点：

从两端向中间扫描，操作对称。
每次交换可能减少两个 “错位” 元素（一个太大、一个太小）。
实现稍复杂，但思路直观，是最常用的分区方式。

单边扫描

单边扫描（One-way Partitioning）从数组的一端向另一端单向扫描，通过维护一个 “小于基准值区域” 的边界来划分元素，步骤如下：

选择基准值：通常选择数组右端的元素作为基准值（pivot）。
初始化边界指针：mark指针指向 “小于基准值区域” 的右边界（初始为low-1）。
遍历数组：用i从low 遍历到 high-1：
- 若arr[i]小于基准值，将mark右移一位，交换arr[mark]与arr[i]（即将当前元素纳入 “小于基准值区域”）。
- 若arr[i]大于等于基准值，不操作，继续遍历。
放置基准值：遍历结束后，将mark右移一位，交换arr[mark]与arr[high]（基准值），此时mark即为基准值的最终位置。

代码示例（单边扫描）：

private static int partitionOneWay(int[] arr, int low, int high) {
    int pivot = arr[high]; // 选择最右元素为基准值
    int mark = low - 1;    // 小于基准值区域的边界（初始为空）
    
    for (int i = low; i < high; i++) {
        // 若当前元素小于基准值，纳入“小于区域”
        if (arr[i] < pivot) {
            mark++;
            swap(arr, mark, i);
        }
    }
    // 将基准值放到最终位置（小于区域的右侧）
    mark++;
    swap(arr, mark, high);
    return mark; // 返回基准值索引
}

特点：

单向遍历，逻辑更简洁，代码行数更少。
只交换 “小于基准值” 的元素，减少不必要的交换。
对缓存更友好（连续访问内存），实际运行效率可能更高。

单边和双边两者对比与适用场景

维度	双边扫描	单边扫描
扫描方向	双向（从两端向中间）	单向（从左到右）
交换次数	较少（一次交换解决两个错位）	较多（只交换小于基准值的元素）
实现复杂度	稍高（需维护两个指针）	较低（单个遍历指针）
缓存友好性	一般（跳跃访问内存）	较好（连续访问内存）
典型基准选择	通常选左端元素	通常选右端元素

适用场景：

双边扫描：适合教学演示，逻辑对称，易于理解。
单边扫描：适合实际工程实现，代码更简洁，缓存效率更高。

两种方式的时间复杂度相同（均为 O (n) per partition），最终都能完成快速排序的分区目标，只是实现细节不同。

代码

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

public class QuickSort {
    
    // 1. 基本版快速排序（以最左元素为基准）
    public static void quickSortBasic(int[] arr, int low, int high) {
        if (low < high) {
            // 分区操作，返回基准值的正确位置
            int pivotIndex = partitionBasic(arr, low, high);
            
            // 递归排序左子数组
            quickSortBasic(arr, low, pivotIndex - 1);
            // 递归排序右子数组
            quickSortBasic(arr, pivotIndex + 1, high);
        }
    }
    
    // 基本版分区函数
    private static int partitionBasic(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选择最左元素作为基准值
        
        // 遍历数组，将小于基准值的元素移到左边
        while (low < high) {
            // 从右向左找到第一个小于基准值的元素
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];
            
            // 从左向右找到第一个大于基准值的元素
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        
        // 将基准值放到正确位置
        arr[low] = pivot;
        return low; // 返回基准值的索引
    }
    
    // 2. 优化版1：随机选择基准值
    public static void quickSortRandomPivot(int[] arr, int low, int high) {
        if (low < high) {
            // 随机选择基准值并与最左元素交换
            randomPivot(arr, low, high);
            int pivotIndex = partitionBasic(arr, low, high);
            
            quickSortRandomPivot(arr, low, pivotIndex - 1);
            quickSortRandomPivot(arr, pivotIndex + 1, high);
        }
    }
    
    // 随机选择基准值
    private static void randomPivot(int[] arr, int low, int high) {
        Random random = new Random();
        int pivotIndex = low + random.nextInt(high - low + 1);
        // 交换随机选择的基准值与最左元素
        swap(arr, low, pivotIndex);
    }
    
    // 3. 优化版2：三数取中法选择基准值
    public static void quickSortMedianPivot(int[] arr, int low, int high) {
        if (low < high) {
            // 三数取中法选择基准值
            medianOfThree(arr, low, high);
            int pivotIndex = partitionBasic(arr, low, high);
            
            quickSortMedianPivot(arr, low, pivotIndex - 1);
            quickSortMedianPivot(arr, pivotIndex + 1, high);
        }
    }
    
    // 三数取中法（首、中、尾三个位置的中间值）
    private static void 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);
        }
        
        // 将中间值放到low位置作为基准值
        swap(arr, low, mid);
    }
    
    // 4. 优化版3：处理重复元素（三向切分）三指针快排：把等于切分元素的所有元素挤到了数组的中间，在有很多元素和切分元素相等的情况下，递归区间大大减少。
    public static void quickSort3Way(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 + 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++;
            }
        }
        
        // 递归排序小于和大于基准值的部分
        quickSort3Way(arr, low, lt - 1);
        quickSort3Way(arr, gt + 1, high);
    }
    
    // 5. 优化版4：小规模数据使用插入排序
    public static void quickSortHybrid(int[] arr, int low, int high) {
        // 当数组长度小于阈值时，使用插入排序
        if (high - low + 1 <= 10) {
            insertionSort(arr, low, high);
            return;
        }
        
        // 否则使用快速排序
        medianOfThree(arr, low, high);
        int pivotIndex = partitionBasic(arr, low, high);
        
        quickSortHybrid(arr, low, pivotIndex - 1);
        quickSortHybrid(arr, pivotIndex + 1, high);
    }
    
    // 插入排序（用于小规模数据）
    private static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    // 交换数组中两个元素的位置
    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 = {64, 34, 25, 12, 22, 11, 90, 5};
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        int[] arr4 = Arrays.copyOf(arr, arr.length);
        int[] arr5 = Arrays.copyOf(arr, arr.length);
        
        quickSortBasic(arr1, 0, arr1.length - 1);
        System.out.println("基本版: " + Arrays.toString(arr1));
        
        quickSortRandomPivot(arr2, 0, arr2.length - 1);
        System.out.println("随机基准值: " + Arrays.toString(arr2));
        
        quickSortMedianPivot(arr3, 0, arr3.length - 1);
        System.out.println("三数取中: " + Arrays.toString(arr3));
        
        quickSort3Way(arr4, 0, arr4.length - 1);
        System.out.println("三向切分: " + Arrays.toString(arr4));
        
        quickSortHybrid(arr5, 0, arr5.length - 1);
        System.out.println("混合插入排序: " + Arrays.toString(arr5));
    }
}

资料

快速排序优化详解

leetcode排序算法讲解三种快排

快速排序实现及pivot的选取