快速排序算法

题目描述
快速排序是一种高效的排序算法，采用分治策略。给定一个数组，快速排序通过选择一个基准元素将数组划分为两部分，使得左边部分的所有元素都小于等于基准，右边部分的所有元素都大于等于基准，然后递归地对左右两部分进行排序，最终得到有序数组。

解题过程

1. 基本思想

   • 分治：将原问题分解为规模更小的子问题。
   • 递归：解决子问题后，合并结果得到原问题的解。
   • 关键操作：划分（Partition），通过一趟排序将数组分割成独立的两部分。

2. 算法步骤

   • 步骤1：选择基准元素（Pivot）。可以从数组中选择第一个元素、最后一个元素、中间元素或随机元素。
   • 步骤2：划分操作。重新排列数组，使得所有小于等于基准的元素移到基准左边，所有大于等于基准的元素移到右边。基准元素位于其最终位置。
   • 步骤3：递归排序。对基准左边的子数组和右边的子数组递归地应用快速排序。

3. 划分操作详解（以Lomuto划分方案为例）

   • 假设选择最后一个元素作为基准（pivot = arr[high]）。
   • 初始化一个索引i，指向小于等于基准的子数组的末尾（初始为low-1）。
   • 遍历数组从low到high-1，对于每个元素arr[j]：
     • 如果arr[j] <= pivot，则i++，并交换arr[i]和arr[j]。
   • 最后，将基准arr[high]与arr[i+1]交换，使基准位于正确位置。
   • 返回基准的索引i+1。

   示例：数组[10, 80, 30, 90, 40, 50, 70]，选择70为基准。

   • 遍历：j=0, 10<=70 → i=0, 交换arr[0]和arr[0] → [10, 80, 30, 90, 40, 50, 70]
   • j=1, 80>70 → 无操作
   • j=2, 30<=70 → i=1, 交换arr[1]和arr[2] → [10, 30, 80, 90, 40, 50, 70]
   • j=3, 90>70 → 无操作
   • j=4, 40<=70 → i=2, 交换arr[2]和arr[4] → [10, 30, 40, 90, 80, 50, 70]
   • j=5, 50<=70 → i=3, 交换arr[3]和arr[5] → [10, 30, 40, 50, 80, 90, 70]
   • 最后交换arr[4]和arr[6]：i+1=4 → [10, 30, 40, 50, 70, 90, 80]，基准70位于索引4。

4. 递归排序

   • 对基准左边的子数组（索引low到pivot_index-1）递归调用快速排序。
   • 对基准右边的子数组（索引pivot_index+1到high）递归调用快速排序。
   • 递归基：当子数组长度为0或1时，已经有序，直接返回。

5. 时间复杂度分析

   • 最佳情况：每次划分均匀，时间复杂度为O(n log n)。
   • 最坏情况：每次划分极不均匀（如数组已有序），时间复杂度为O(n²)。
   • 平均情况：时间复杂度为O(n log n)。

6. 优化策略

   • 随机选择基准：避免最坏情况发生。
   • 三数取中：选择首、中、尾元素的中位数作为基准。
   • 小数组使用插入排序：当子数组规模较小时（如长度<10），插入排序更高效。
   • 尾递归优化：减少递归深度。

7. 代码实现（Java）

public class QuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high); // 划分操作
            quickSort(arr, low, pi - 1);  // 递归排序左半部分
            quickSort(arr, pi + 1, high); // 递归排序右半部分
        }
    }

    private 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 void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

通过以上步骤，你可以理解快速排序的核心思想、划分过程以及如何通过递归实现整个排序算法。