quicksort - K&R 快速排序代码

Question

我检查了 K&R 书中的快速排序代码，2 小时后我仍然无法理解第一个交换 (swap(a, left, (left+right)/2);) 实现的内容.我尝试删除它，但排序仍然有效。有人可以解释吗？这是性能问题吗？如果是这样，为什么？这个 Action 对我来说似乎是随机的(也就是说，在某些数字组上它会提高性能，而在某些数字上则不会)。

谢谢。

void qsort(int a[], int left, int right)
{
    int i, last;

    if (left >= right)
        return;

    swap(a, left, (left+right)/2);

    last = left;
    for (i = left + 1; i <= right; i++)
        if(a[i] < a[left])
             swap(a, ++last, i);

   swap(a, left, last);
   qsort(a, left, last-1);
   qsort(a, last+1, right);
}

Answer 1

它将枢轴元素放在子数组的第一个位置。

然后继续围绕枢轴对子数组进行分区，这样分区完成后，子数组如下所示:[pivot, [elements < pivot], [elements >= pivot]] .

之后，将主元简单地放入适当的空间，因此子数组如下所示:[[elements < pivot], pivot, [elements >= pivot]] .

然后，递归调用两个子子数组。

无论选择哪个元素作为基准，快速排序始终有效。问题是，如果您选择中值元素，那么时间复杂度将是线性的 (O(nlogn))。但是，如果您选择最大的元素作为基准，则性能将降级为二次 (O(n^2))。

因此，从本质上讲，主元选择是快速排序性能的关键，但它会起作用(当我说起作用时，我的意思是你最终会得到一个排序的数组)。