c++ - 就地快速基数排序实现

Question

我正在阅读以下链接中的二进制快速排序算法

http://www.cs.princeton.edu/courses/archive/spr02/cs226/lectures/radix.4up.pdf

quicksortB(int a[], int l, int r, int w)
{ 
   int i = l, j = r;
   if (r <= l || w > bitsword) return;
   while (j != i)
   {
     while (digit(a[i], w) == 0 && (i < j)) i++;
     while (digit(a[j], w) == 1 && (j > i)) j--;
     exch(a[i], a[j]);
   }
   if (digit(a[r], w) == 0) j++;  //** question here.**
   quicksortB(a, l, j-1, w+1);
   quicksortB(a, j, r, w+1);
}

我的问题是，为什么在提供 while 循环后进行额外检查。要求举例说明何时以及为何需要此条件。

Answer 1

当分区中的所有元素都具有相同的 digit(a[...], w) 时会发生什么？

发生这种情况时，在 while (j != i) 循环之后，j 将指向该分区的最后一个元素，因此 quicksortB( a, l, j-1, w+1) 会将该元素排除在外，而 quicksortB(a, j, r, w+1) 会用一个元素对范围进行排序。

不过，在这种特殊情况下，您需要将所有具有相同前导数字的元素放入一个分区中，以便第一个 quicksortB() 调用对它们进行排序。当您这样做时，第二个 quicksortB() 将获得一个空分区并且什么都不做，这是安全的。这就是您突出显示的 if 语句所完成的。

换句话说，if 语句基本上是说“好的，基数排序在这个级别上什么也没做，所以让我们在下一个数字处再试一次，所有元素都在一个分区中。”

如果您不这样做，那么您遗漏的元素将无法正确排序，因为您仅按基数排序中感兴趣的数字进行了分区。