C/C++快速排序算法：从分区逻辑到递归实现的完整解析

// 交换辅助函数
void swap(int* a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 分区函数
// 参数说明:
// a: 待排序数组指针
// left: 子数组起始索引
// right: 子数组结束索引
int partition(int* a, int left, int right) {
    // 选择最左边的元素作为基准
    int pivot = left; 
    // index记录“小于基准值”区域的右边界下一位
    int index = left + 1;
    
    // 遍历除基准外的所有元素
    for (int i = index; i <= right; i++) {
        // 如果当前元素小于基准值，则将其交换到index位置，并扩大左侧小元素区域
        if (a[i] < a[pivot]) {
            swap(a, i, index);
            index++;
        }
    }
    
    // 将基准值交换到它应该在的位置（即index-1处）
    // 因为index指向的是第一个大于等于基准值的位置，所以index-1是最后一个小于基准值的位置
    swap(a, pivot, index - 1);
    
    // 返回基准值的最终索引
    return index - 1;
}

// 快速排序主函数
// 参数说明:
// a: 待排序数组指针
// left: 当前处理子数组的起始索引
// right: 当前处理子数组的结束索引
void quick_sort(int* a, int left, int right) {
    // 递归终止条件：子数组只有一个或零个元素
    if (left < right) {
        // 1. 进行分区，获取基准值的最终索引
        int pivot_index = partition(a, left, right);
        
        // 2. 递归排序基准值左侧的部分
        quick_sort(a, left, pivot_index);
        
        // 3. 递归排序基准值右侧的部分
        // 注意：pivot_index处的元素已经排好序，右侧从 pivot_index + 1 开始
        quick_sort(a, pivot_index + 1, right);
    }
}