快速排序递归图解

### 快速排序算法递归实现的详细图解说明

快速排序是一种基于分治法思想的经典排序算法，它通过选取一个基准值（pivot），将数组划分为两部分：一部分小于等于基准值，另一部分大于基准值。接着对这两部分分别递归调用快速排序，最终得到有序序列。

#### 基本概念
快速排序的核心在于单趟排序操作，即如何选择合适的基准值并将数据分区[^2]。通常采用左右指针法完成这一过程。以下是具体步骤：

1. **选定基准值**：一般可以选择第一个元素作为基准值。
2. **划分区间**：利用双指针技术调整数组中的元素位置，使左侧均不大于基准值，右侧均不小于基准值。
3. **递归处理子区间**：针对上述两个子区间重复执行相同的操作直到无法继续分割为止。

#### 图解示例
假设有一个待排序数组 `arr=[8, 4, 7, 9, 3, 2, 6, 5]` ，下面展示其递归过程中每一步的变化情况:

初始状态:`[8, 4, 7, 9, 3, 2, 6, 5]`

- 第一次划分:
- 设定左边界l=0,右边界r=7,pivot=arr[l]=8.
- 移动左右指针直至找到满足条件的位置互换元素(此处省略中间细节),最后结果为:`[5, 4, 7, 6, 3, 2, 8, 9]`,此时div=6.

第二次划分之前的状态变为两个独立区域:[5, 4, 7, 6, 3, 2](<8) 和 [9](>8).

对于左边区域 `[5, 4, 7, 6, 3, 2]` 进行同样的操作...

以此类推，不断缩小范围直至整个列表完全有序。

#### C语言代码实现
下面是完整的C语言版本的递归实现方式：

void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high){
    int pivot = arr[high];  
    int i = (low - 1);  

    for (int j = low; j <= high- 1; j++){
        if (arr[j] <= pivot){
            i++;    
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

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); 
    }
}

此段程序定义了一个辅助函数用于交换数值以及主要逻辑所在的partition()和quickSort().其中partition负责实际的数据移动与定位新的中心点；而quickSort则控制整体流程并决定何时停止进一步拆分[^4].

#### 性能分析
理论上讲，在理想状况下每次都能均匀分配左右两侧，则总体耗时接近O(n log n)[^3].然而现实中由于输入特性差异可能导致极端情形发生比如已经近乎升序排列的情况下退化至平方级效率O(n²).因此实践中还需考虑其他因素如稳定性需求等因素综合评判选用何种具体的变种形式更为合适。