K＆R快速排序代码

Question

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

谢谢。

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））。因此，本质上，枢轴选择是Quick-Sort性能的关键，但它会起作用（当我说工作时，我的意思是最终会得到一个有序数组）。

Answer 2

K & R实现为中心选择中间索引（即(left+right)/2）。取消这一行代替使用最左边的元素。实现仍然有效，但是当数组已经排序后，性能会下降。

Wikipedia article说明这一点：

在快速排序的非常早期版本中，分区的最左边的元素往往会被选择作为枢转元件。不幸的是，这会导致已排序数组的最坏情况行为，这是一种相当常见的用例。这个问题很容易解决，方法是选择一个随机索引作为主键，选择分区的中间索引或者（特别是对于更长的分区），选择分区的第一个，中间和最后一个元素的中位数（如塞奇威克）。