十大排序之快速排序

交换法

交换法快速排序的步骤

1、找到一个分界点，让分界点左边的值小于分界点，右边的值大于等于分界点。

2、对做左边这样做。

3、对右边在这样做。

核心代码

    # 非完整代码
    private static int partition2(int[] arr, int left, int right) {
        int i = left, j = right;
        int pivot = arr[left];
        while (i < j) {
             while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        swap(arr, left, i);
        return i;
    }

Q&A

为什么是从后往前走，能不能换一下位置？

1、因为我们选择的标兵是在左侧，所以我们要从右侧开始遍历

那为什么因为我们选择的标兵是在左侧，就要从右边开始?

进一步的分析，我们最终需要将标兵把i==j停下来的位置的值做交换，所以停下来的位置，一定要是比标兵更小的值，否则就不满足，标兵左边的值小于标兵的前提。假定如果我们从左开始，那么就有最终在比标兵大的地方停下来，导致最终发生交换的时候违背了前面说的原则。而从右边开始我们能够保证一定是遇到比标兵小的值或者回到标兵的位置才停下来。

2、如果你希望从左边开始，那么标兵选择最右边即可。