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

无论如何，分区函数的工作原理如下：假设我们有大小为 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 放在第一个元素上，因为我们仍然不知道该元素是大于还是小于 pivot

2,4,5,1,3
^

一旦我们意识到 2 不是 而不是 大于主元的第一个元素，或者我们在该位置交换一个小于主元的元素，我们试图保持我们的不变量有效：ok，推进 firsthigh 并将 4 视为大于 pivot 的第一个元素。这给了我们教科书中引用的三个部分。

Answer 2

在任何时候，都知道 firstHigh 严格左侧的所有内容都小于主元（请注意，此集合中最初没有元素），以及它右侧或右侧的所有内容是未知的，或者已知 >= 枢轴。将 firstHigh 视为下一个我们可以放置低于枢轴的值的位置。

此算法与原地算法非常相似，您可以使用该算法删除 >= 主元的所有项目，同时 "compacting" 剩余项目尽可能向左删除。对于后者，您将维护两个从 0 开始的索引 l 和 firstHigh（您可以分别将其视为 from 和 to），然后遍历 l通过数组；每当你遇到一个 不应该 被删除的 s[l] 时，你将它尽可能地向左分流：即，你将它复制到 s[firstHigh] 然后你递增 firstHigh。这是安全的，因为我们总是有 firstHigh <= l。这里唯一的区别是我们无法覆盖当前位于 s[firstHigh] 的已删除（可能->=-to-pivot）项目，因此我们交换这两个项目。

Skiena 的快速排序实现

Skiena's Quick Sort implementation

c

sorting

algorithm

quicksort