LeetCode-多语言实现快速排序以及算法优化改进

一、快速排序算法

快速排序（Quick Sort）是一种高效的分治排序算法，由英国计算机科学家 Tony Hoare 于 1960 年提出。是 实际应用中最常用的排序算法之一 。快速排序基本思想是：选择一个”基准”（pivot）元素，通过一次排序将待排序列分割成独立的两部分，一部分所有元素均小于基准，另一部分所有元素均大于基准，然后递归地对这两部分分别进行快速排序。分治策略的运用让快速排序在平均情况下能达到 O(nlogn) 的时间复杂度，大大优于简单排序算法的 O(n²) 性能。

时间复杂度:最佳 O(n log n) | 平均 O(n log n) | 最差 O(n²)

空间复杂度:O(log n)

稳定性:不稳定

算法步骤

从数列中选择一个元素作为”基准”（pivot），本文采用最左侧元素作为基准
将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（分区操作）
对基准左右两个子序列分别重复步骤1和2，直到子序列只有一个元素或为空

二、应用场景/核心特性

分治策略：将问题分解为更小的子问题，逐步解决
原地排序：只需要 O(logn) 的额外空间复杂度（主要用于递归调用的栈空间）
时间复杂度：平均情况为 O(nlogn)，最坏情况为 O(n²)，最好情况为 O(nlogn)
不稳定性：相等元素的相对位置在排序后可能会改变
高效性：在实际应用中，快速排序通常是最快的排序算法之一

优缺点

优点

平均情况下非常高效，时间复杂度为 O(nlogn)
原地排序，空间复杂度低
缓存友好，数据局部性好
适合处理大规模数据
在许多实际应用中表现优秀

缺点

最坏情况下性能退化至 O(n²)，比如当数组已经排序时
不稳定的排序算法
对于小数组，快速排序可能比其他基础排序慢
递归实现可能导致栈溢出（可以使用迭代方式解决）

应用场景

需要高效排序大量数据的情况
作为系统库中的排序函数（如 C++ 的 std::sort、Java 的 Arrays.sort）
需要就地排序且对空间复杂度敏感的场景
需要平均情况下高性能的应用

三、经典算法实现并优化改进

public class QuickSort {
    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);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        // 选择最左侧元素作为基准
        int pivot = arr[low];
        int i = low + 1;
        
        for (int j = low + 1; j <= high; j++) {
            // 将小于基准的元素移到左侧
            if (arr[j] < pivot) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        
        // 将基准元素放到正确位置
        int temp = arr[low];
        arr[low] = arr[i - 1];
        arr[i - 1] = temp;
        
        return i - 1;
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前的数组：");
        printArray(arr);
        
        quickSort(arr, 0, arr.length - 1);
        
        System.out.println("排序后的数组：");
        printArray(arr);
    }
}

注意，在上述代码里，通过：

for (int j = low + 1; j <= high; j++) {
    // 将小于基准的元素移到左侧
    if (arr[j] < pivot) {
        // 交换元素
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
    }
}

将小于基准的元素移到左侧，然后通过：

int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;

优化策略

随机选择基准元素

使用最左侧元素作为基准可能会在数组已经排序或接近排序时导致最坏性能，随机选择基准可以降低这种风险：

private static int randomPartition(int[] arr, int low, int high) {
    // 随机选择基准元素位置
    int randomIndex = low + (int)(Math.random() * (high - low + 1));
    
    // 将随机选择的基准元素与最左侧元素交换
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[low];
    arr[low] = temp;
    
    // 使用标准分区过程
    return partition(arr, low, high);
}

三数取中法

选择左端、中间和右端三个元素的中值作为基准，可以进一步优化快速排序：

private static int medianOfThreePartition(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    // 对三个元素进行排序
    if (arr[mid] < arr[low])
        swap(arr, mid, low);
    if (arr[high] < arr[low])
        swap(arr, high, low);
    if (arr[high] < arr[mid])
        swap(arr, high, mid);
    
    // 将中值（现在在arr[mid]）放到arr[low]
    swap(arr, mid, low);
    
    // 使用标准分区过程
    return partition(arr, low, high);
}

双轴快速排序(Dual-Pivot QuickSort)

双轴快速排序是传统快速排序的改进版本，由Vladimir Yaroslavskiy在2009年提出，它使用两个枢轴(pivot)将数组分成三个部分，而不是传统快速排序的一个枢轴分成两部分。这种算法在Java 7中被用作默认的数组排序算法。

Java 的 Arrays.sort() 使用的是双轴快速排序，它使用两个枢轴(基准)，可以进一步提高性能：

// 双轴快速排序方法，参数为数组、起始索引和结束索引
public static void dualPivotQuickSort(int[] arr, int low, int high) {
    // 递归终止条件：当high <= low时，表示子数组长度为0或1，无需排序
    if (high <= low) return;
    
    // 确保第一个枢轴(pivot1)不大于第二个枢轴(pivot2)
    // 如果arr[low] > arr[high]，交换它们的位置
    if (arr[low] > arr[high]) {
        int temp = arr[low];  // 临时变量用于交换
        arr[low] = arr[high];
        arr[high] = temp;
    }
    
    // 设置两个枢轴值
    int pivot1 = arr[low];   // 较小的枢轴，位于数组起始位置
    int pivot2 = arr[high];  // 较大的枢轴，位于数组结束位置
    
    // 初始化分区指针
    int lt = low + 1;    // 小于pivot1区域的右边界，初始指向low+1
    int gt = high - 1;   // 大于pivot2区域的左边界，初始指向high-1
    int i = low + 1;     // 当前正在处理的元素指针，初始指向low+1
    
    // 开始分区过程
    while (i <= gt) {
        // 情况1：当前元素小于第一个枢轴(pivot1)
        if (arr[i] < pivot1) {
            // 将当前元素交换到小于pivot1的区域
            int temp = arr[lt];
            arr[lt] = arr[i];
            arr[i] = temp;
            lt++;  // 扩大小于pivot1的区域
            i++;   // 处理下一个元素
        } 
        // 情况2：当前元素大于第二个枢轴(pivot2)
        else if (arr[i] > pivot2) {
            // 将当前元素交换到大于pivot2的区域
            int temp = arr[i];
            arr[i] = arr[gt];
            arr[gt] = temp;
            gt--;  // 扩大大于pivot2的区域
            // 注意：这里不增加i，因为交换过来的新元素需要重新检查
        } 
        // 情况3：当前元素在两个枢轴之间
        else {
            i++;  // 只需移动到下一个元素
        }
    }
    
    // 将两个枢轴放到它们的最终位置
    
    // 将pivot1放到正确位置
    // 先将arr[low]的值保存到lt-1的位置
    arr[low] = arr[lt - 1];
    // 然后将pivot1放到lt-1的位置
    arr[lt - 1] = pivot1;
    
    // 将pivot2放到正确位置
    // 先将arr[high]的值保存到gt+1的位置
    arr[high] = arr[gt + 1];
    // 然后将pivot2放到gt+1的位置
    arr[gt + 1] = pivot2;
    
    // 递归处理三个子数组
    
    // 递归处理左子数组：小于pivot1的部分
    // 范围是从low到lt-2（因为lt-1是pivot1的位置）
    dualPivotQuickSort(arr, low, lt - 2);
    
    // 递归处理中子数组：介于pivot1和pivot2之间的部分
    // 范围是从lt到gt
    dualPivotQuickSort(arr, lt, gt);
    
    // 递归处理右子数组：大于pivot2的部分
    // 范围是从gt+2到high（因为gt+1是pivot2的位置）
    dualPivotQuickSort(arr, gt + 2, high);
}

算法步骤解析：

‌基本情况处理‌：如果high <= low，直接返回
‌选择并调整枢轴‌：确保arr[low] <= arr[high] ，双枢轴选择‌：算法选择数组的第一个和最后一个元素作为两个枢轴，确保pivot1 ≤ pivot2。
‌初始化指针‌：

pivot1 = arr[low] (较小的枢轴)
pivot2 = arr[high] (较大的枢轴)
lt = low + 1 (小于pivot1区域的右边界)
gt = high – 1 (大于pivot2区域的左边界)
i = low + 1 (当前处理元素的指针)

‌分区过程‌：

当前元素 < pivot1：交换到lt位置，lt和i都右移
当前元素 > pivot2：交换到gt位置，gt左移
否则：i右移

‌放置枢轴‌：将pivot1和pivot2放到正确位置

小于pivot1的元素放在最左边
大于pivot2的元素放在最右边
介于pivot1和pivot2之间的元素放在中间

lt指针跟踪小于pivot1区域的边界
gt指针跟踪大于pivot2区域的边界
i指针遍历当前元素

‌递归排序‌：对三个子数组递归排序

让我们用数组 [24, 8, 42, 75, 29, 77, 38, 57] 来演示排序过程：

初始调用 dualPivotQuickSort(arr, 0, 7)

初始数组: [24, 8, 42, 75, 29, 77, 38, 57]

检查并交换枢轴：24 < 57，无需交换

pivot1 = 24, pivot2 = 57

lt = 1, gt = 6, i = 1

分区过程：

i=1: 8 < 24 → 交换arr[1]和arr[1] (无变化),

lt=2, i=2i=2: 42 ∈ [24,57] → i=3

i=3: 75 > 57 → 交换arr[3]和arr[6] → [24,8,42,38,29,77,75,57], gt=5

i=3: 38 ∈ [24,57] → i=4

i=4: 29 ∈ [24,57] → i=5

i=5: 77 > 57 → 交换arr[5]和arr[5] (无变化), gt=4

循环结束(i=5 > gt=4)

放置枢轴：