c - Skiena 的快速排序实现

Question

我发现很难理解 Skiena 的快速排序。具体来说，他正在使用 partition 函数，尤其是 firsthigh 参数做什么？

quicksort(item_type s[], int l, int h) {
    int p;                  /* index of partition */
    if ((h - l) > 0) {
            p = partition(s, l, h);
            quicksort(s, l, p-1);
            quicksort(s, p+1, h);
    }
}

We can partition the array in one linear scan for a particular pivot element by maintaining three sections of the array: less than the pivot (to the left of firsthigh), greater than or equal to the pivot (between firsthigh and i), and unexplored (to the right of i), as implemented below:

int partition(item_type s[], int l, int h) {

    int i;           /* counter */
    int p;           /* pivot element index */
    int firsthigh;   /* divider position for pivot element */

    p = h;
    firsthigh = l;
    for (i = l; i  <h; i++) {
        if (s[i] < s[p]) {
            swap(&s[i],&s[firsthigh]);
            firsthigh ++;
        }

    swap(&s[p],&s[firsthigh]);
    return(firsthigh);
}

Answer 1

_{我建议在阅读此答案及其考虑的示例时，用铅笔和纸进行推理}

代码片段中缺少一些括号:

int partition(item_type s[], int l, int h)
{
  int i;/* counter */
  int p;/* pivot element index */
  int firsthigh;/* divider position for pivot element */
  p = h;
  firsthigh = l;
  for (i = l; i < h; i++) {

    if (s[i] < s[p]) {
      swap(s[i], s[firsthigh]);
      firsthigh++;
    }
  }

  swap(s[p], s[firsthigh]);
  return(firsthigh);
}

void quicksort(item_type s[], int l, int h)
{
  int p;                  /* index of partition */
  if ((h - l)>0) {
    p = partition(s, l, h);
    quicksort(s, l, p - 1);
    quicksort(s, p + 1, h);
  }
}

无论如何，分区函数的工作原理如下:假设我们有数组 { 2,4,5,1,3 }大小为 5。算法获取最后一个元素 3作为枢轴并开始迭代地探索项目:

2第一次遇到..自 2小于主元元素3 ，它与 firsthigh 指向的位置 0 交换。自 2 起这没有任何影响已经在位置 0

2,4,5,1,3
^

firsthigh自2开始递增现在是该位置的稳定值。

然后4遇到。这次4大于3 (比枢轴)所以不需要交换。请注意 firsthigh继续指向4 。 5 也会发生同样的情况.

何时 1遇到时，该值应放在2之后，因此它与 firsthigh 指向的位置交换，即 4的位置

2,4,5,1,3
  ^   ^ swap
2,1,5,4,3
    ^ now firsthigh points here

当元素结束时，主元元素会与 firsthigh 交换的位置，因此我们得到

2,1,| 3,| 4,5

请注意小于主元的值如何放置在左侧，而大于主元的值保留在右侧。正是配分函数所期望的。

返回主元元素的位置，并在主元左右的子数组上重复该过程，直到遇到一组 0 元素(if 条件是递归的底部)。

因此firsthigh意思是:第一个大于我所知道的主元的元素。在上面的例子中firsthigh被放在第一个元素上，因为我们仍然不知道该元素是大于还是小于枢轴

2,4,5,1,3
^

一旦我们意识到2是不是第一个大于主元的元素，或者我们在该位置交换小于主元的元素，我们尝试保持不变式有效:ok，前进firsthigh并考虑4作为大于主元的第一个元素。这为我们提供了教科书中引用的三个部分。