Sedgewick Quicksort 没有完全意义

Question

我了解快速排序的概念，而且我看到的大多数实现对我来说都非常有意义。但是 Robert Sedgewick 没有，他的实现是这样的：

        private void sort(int lo, int hi) { 
            if (hi <= lo) return;
            int j = partition(lo, hi);
            sort(lo, j-1);
            sort(j+1, hi);
        }

        private int partition(int lo, int hi) {
            int start = lo;
            int partition = hi + 1;
            int pivot = theArray[lo];
            while (true) { 

                // left to right
                while (less(theArray[++start], pivot))
                    if (start == hi) break;

                // right to left
                while (less(pivot, theArray[--partition]))
                    if (partition == lo) break;  

                // check if pointers cross
                if (start >= partition) break;

                exch(theArray, start, partition);
            }

            // place pivot at partition
            exch(theArray, lo, partition);

            return partition;
        }

        private boolean less(int v, int w) {
            return v < w;
        }

        private void exch(int[] a, int i, int j) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }

除了分区函数，我都懂了。特别是 while(true) 部分

中发生的事情

Answer 1

让我们做一些"brain debug"

int pivot = theArray[lo];
将第一个元素固定为枢轴值

while (less(theArray[++start], pivot)) if (start == hi) break;
找到要交换的第一个元素 - 最左边的那个大于 pivot

while (less(pivot, theArray[--partition])) if (partition == lo) break;
查找第二个元素进行交换——最右边小于pivot

if (start >= partition) break;
当没有更多元素要交换时中断 while (true) 循环

exch(theArray, start, partition);
找到交换元素

示例[5 3 8 9 2]：
5 是枢轴
第一个 'bad' 元素是 8
第二个是 2
他们交换了

[5 3 2 9 8]

现在第一个index停在4（hi），第二个index停在2，loop breaks，5次换2。

结果：[2 3 5 9 8]
子范围 (2,3,5) 和 (9,8) 是新分区

Sedgewick Quicksort 没有完全意义

Sedgewick Quicksort not making total sense

java

sorting

algorithm

quicksort