快速排序分区：如何获得正确的枢轴，正确的第一和其他变化工作

Question

我是高中学习APCS课程的学生，为我的中期学习。我的老师说下面是编码“升序排序 - 选择正确的枢轴，当分区看左边第一个/降序排序 - 选择左侧枢轴和分区时看右边第一个”的最佳编码方式

起初我无法理解为什么所以我只是尝试了所有我为Ascending Sorting尝试过的案例

（1）选择正确的枢轴/首先看左边

（2）选择正确的枢轴/先看右边

（3）选择左侧枢轴/首先看左侧

（4）选择左转轴/先看右边

但我只有（1）类型才能工作。其余3个版本中存在一些逻辑错误。根据经验，我知道（2）〜（4）更难编码根据经验和写在纸上我知道如果我使用正确的枢轴并首先看右边使用QuickSort的常规方法会有问题。

总结：问题[1]版本（2）〜（4）比（1）更难编码的确切原因是什么？ [2]你们中任何一个神奇的程序员都可以帮我完成（2）〜（4）

这是在java中工作的版本（1）的代码

///* MOST SIMPLE VERSION OF QUICKSORT. ASCENDING, END PIVOT, LEFT FIRST 
SWEEP, LEFT & RIGHT COMPARISON
    public static void endPivSortV1(int[] a, int start, int end) {
        if(start < end) {
            int pVal = a[end];
            int left = start;
            int right = end; 
            //QUESTION: right = end - 1 

            while(true) {
                while(a[left] <= pVal && left < right) //left, 
                    left++;

                while(a[right] >= pVal && left < right)
                    right--;

                if(left == right)
                    break;

                swap(a, left, right);
            }
            swap(a, left, end);

            endPivSortV1(a, start, left - 1);
            endPivSortV1(a, left + 1, end);
        }   
    } //*/

我复制并粘贴了这段代码并改变了它的一点来创建版本（2）〜（4）但它们不起作用。

public static void endPivSortV2(int[] a, int start, int end) {
        if(start < end) {
            int pVal = a[end];
            int left = start - 1;
            int right = end + 1;

            while(true) {
                while(a[right--] >= pVal && left < right);

                while(a[left++] <= pVal && left < right);

                if(left == right)
                    break;

                swap(a, left, right);
            }
            swap(a, left, end);

            endPivSortV2(a, start, left - 1);
            endPivSortV2(a, left + 1, end);
        }   
    }

这是我试图先看右边而不是左边的那个。 （改变右边的句子位于左边的那个句子的前面）我知道代码是超级马虎并且充满了错误但是因为我在高中只编写了1年的非常兼职...

谢谢。这是我在这里发表的第一篇文章，所以不要对我太过刻意：D

Answer 1

（1）和（4）基本相同，你可以指望扫描运行到枢轴值作为一种停止循环的方式，而不必进行边界检查。对于（1），... <pivot如果到达右侧的枢轴，将停止。对于（4），...>如果到达左侧的枢轴，枢轴将停止。

（2）和（3）需要检查，因此扫描的索引不会超出数组的范围，或者您可以通过将数据线交换到数组的另一端并使用（1中的逻辑）来“欺骗” ）或（4）。

注意 - 所有这些都是Lomuto分区方案的变体。还有Hoare分区方案，它通常选择中间值作为枢轴，并从左侧和右侧扫描（使用单独的索引进行两次扫描）。当索引彼此交叉时，扫描停止。