分治范式下的快速排序全解：C++实现、时间复杂度优化与工程化实践

目录

一、算法原理与分治思想

二、关键操作：分区算法

1. Lomuto分区法（经典实现）

2. Hoare分区法（原始实现）

三、时间复杂度分析

四、关键优化策略

五、稳定性与空间复杂度

六、完整C++实现

七、算法扩展：三路快速排序

八、性能对比测试数据

九、工程实践建议

一、算法原理与分治思想

快速排序采用典型的分治策略（Divide-and-Conquer），核心操作分为三个阶段：

1. 分解（Partitioning）

   • 选定基准元素（pivot）

   • 将数组划分为两个子区间：左区间的元素均 ≤ pivot，右区间的元素均 ≥ pivot

2. 递归求解

   • 对左右子区间递归执行快速排序

3. 合并（Implicit Merge）

   • 由于排序在分解过程中完成，无需显式合并操作

     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); // 处理右区间
         }
     }

二、关键操作：分区算法

1. Lomuto分区法（经典实现）

核心思想：通过单次遍历完成元素分类

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], arr[j]);   // 将小元素交换到左区
        }
    }
    swap(arr[i + 1], arr[high]);    // 基准归位到正确位置
    return i + 1;                   // 返回基准索引
}

实例分析（数组[3,1,4,2,5]）：

初始状态：i=-1, pivot=5
j=0: 3<=5 → i=0 → swap(arr[0],arr[0]) → 无变化
j=1: 1<=5 → i=1 → swap(arr[1],arr[1]) → 无变化
j=2: 4<=5 → i=2 → swap(arr[2],arr[2]) → 无变化
j=3: 2<=5 → i=3 → swap(arr[3],arr[3]) → 无变化
最终交换arr[4]与arr[4] → 基准归位

2. Hoare分区法（原始实现）

优势：减少元素交换次数，适合存在大量重复元素的场景