c - qsort 是如何工作的？

Question

有人可以解释这种排序算法的作用吗？我无法遵循逻辑，它使用递归。取中间词并将其与第一行（从顶部开始的第 8 行）交换似乎很奇怪。此外，在第一次迭代中，++last = i, 所以对 swap 的调用被浪费了。

代码设置last = left, i = left + 1，然后调用 swap() ++last。这使得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

代码中的注释非常解释。开始时，选择了一个“分区”元素并将其移动到数组的开头，这样后续的交换就不会触及它。然后所有剩余的元素都被部分排序，因此这个“分区”元素可以插入到排序数组中的最终位置，这就是最后一次交换所做的事情（就在为左边和右边的部分调用递归之前）分区元素）。

有关算法的详细信息，请阅读快速排序。