关于《C程序设计语言》中qSort函数工作原理的技术问询

先纠正个小细节：你提到的这个是快速排序函数，不是希尔排序——第5.6章讲的是用指针实现快速排序，应该是笔误啦。

你的疑问核心是：循环里swap(v, ++last, i)会不会出现++last等于i、交换同一个数组单元的情况？确实会，但这是代码故意的简洁写法，完全不影响逻辑，下面拆解给你看：

修正后完整代码（原代码末尾多了一个多余大括号，已去除） #

/* qsort: sort v[left]...v[right] into increasing order */
void qSort(void *v[], int left, int right, int (*comp)(void *, void *))
{
    int i, last;

    void swap(void *v[], int, int);

    if (left >= right)             /* do nothing if array contains */
        return;                    /* fewer than two elements */
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qSort(v, left, last - 1, comp);
    qSort(v, last + 1, right, comp);
}

void swap(void *v[], int i, int j)
{
    void *temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

逐段拆解逻辑 #

1. 基准元素初始化：
   swap(v, left, (left + right) / 2) 把数组中间位置的元素交换到left位置，用它作为快速排序的基准元素——这么做是为了避免数组已有序时的低效排序情况。

2. 分区循环的核心逻辑：

   • last初始化为left（基准元素的位置），它用来标记「所有比基准小的元素组成的区域」的最后一个位置。
   • 循环从i = left + 1开始遍历到right：
     • 如果当前元素v[i]比基准v[left]小，先把last向后挪一位（++last），再把v[i]和v[last]交换。
     • 当连续遇到多个比基准小的元素时，比如第一个i=left+1就满足条件，++last后刚好等于i，这时候交换的是同一个位置——但swap函数里即使i==j，执行的也是temp=v[i]; v[i]=v[j]; v[j]=temp，等于没做任何操作，完全不影响结果。代码故意这么写，是为了省去「判断++last是否等于i」的额外逻辑，保持简洁。

3. 基准归位与递归排序：
   循环结束后，last的位置就是基准元素应该在的正确位置——左边全是比它小的元素，右边全是比它大的。这时候把基准元素（left位置）和last位置交换，然后递归排序left到last-1、last+1到right这两个子数组即可。

简单说：即使出现++last == i的情况，也只是做了一次无意义的交换，但不会破坏排序逻辑，反而让代码更简洁——这正是K&R代码的风格：用最少的代码实现正确的逻辑，哪怕包含一些无害的冗余操作。

内容的提问来源于stack exchange，提问作者Huntermor