c - qsort 是如何工作的？

Question

谁能解释一下这种排序算法的作用？我无法遵循逻辑，它使用递归。把中间项和第一个(从上数第 8 行)交换起来似乎很奇怪。另外，在第一次迭代中，++last = i，因此对 swap 的调用被浪费了。

代码设置last = left，i = left + 1，然后用++last调用swap()。这使得 last 等于 i!

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

    if (left >= right) /* do nothing if array contains */
        return; /* fewer than two elements */

    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                     /* to v[0] */

    for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last); /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

Answer 1

代码中的注释解释得很清楚。开始时，选择一个“分区”元素并将其移动到数组的开头，以便后续交换不会触及它。然后对所有剩余元素进行部分排序，以便可以将此“分区”元素插入到已排序数组中的最后位置，这就是最后一个交换所做的(就在对左侧和右侧的部分调用递归之前)分区元素)。

有关算法的详细信息，请阅读 Quick sort .