c - Skiena的快速排序实现

我发现很难理解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);
    }
}

  我们可以通过维护数组的三个部分，在一个线性扫描中为特定的枢轴元素划分数组：小于枢轴（在firsthigh的左侧），大于或等于枢轴（在firsthigh和）和未开发（在i右侧），如下所示：

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);
}

最佳答案

在阅读此答案及其经过考虑的示例案例时，我建议您使用铅笔和纸进行推理

摘录中缺少一些括号：

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);
  }
}

无论如何，分区功能的工作方式如下：假设我们有大小为5的数组{ 2,4,5,1,3 }。该算法将最后一个元素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不是大于枢轴的第一个元素，或者我们在该位置交换了小于枢轴的元素，我们将尝试使我们的不变式有效：好的，将firsthigh前进并考虑4作为第一元素大于枢轴。这给了我们教科书中引用的三个部分。