关于快排

最近在撸快排，发现网上写的千篇一律，理论定义的步骤和代码稍有些区别，所以按我自己理解的在整理一遍
首先抄一下网上的定义和模拟图：

• 从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
• 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
  image.png
  从动图就可以看到开始时候基准为array[0]，当比较比array[0]小时，放到array[0]后面，
  image.png
  现在有这么个数组：
  [6,2,9,3,5,1,7]
  如果我们按理论的来应该这么做：
  step1：将pivot设为第一个值6，找到比6小的值2：[6,2,9,3,5,1,7]
  step2：将2放到6前面[2,6,9,3,5,1,7]
  step3：同上将3放到6前面[2,3,6,9,5,1,7]
  ... : [2,3,1,5,6,9,7]
  然后将2，9(6的下一个)作为pivot递归继续
  这是正常人理解的定义步骤，但却不是代码实现步骤...
  因为你会发现，如果将2放在6前面，需要将2之前的整个数组往后移一位，增加了复杂度。

那么实际代码处理是怎么样的？
用了一个取巧的方式，增加一个指针，将比pivot小的数放到pivot后面，指针后移，最后将pivot和最后的指针位置交换下就可以了。
那么我们来看：
step1：相同，将pivot设为第一个值6，找到比6小的值2：[6,2,9,3,5,1,7]，增加一个指针指向pivot后面的位置(下标1)
step2：将2和指针互换位置，由于这里是同一个，不变[6,2,9,3,5,1,7]，指针后移到下标2
step3：找到下一个值3，和下标2的值9换位，[6,2,3,9,5,1,7]指针后移到下边3
step4：同上找到5，对列变为[6,2,3,5,9,1,7]，指针后移到4
step5：[6,2,3,5,1,9,7],指针到5
step6：将6和最后一个小于6(即是指针之前的一位下标5-1=4)的值换位[1,2,3,5,6,9,7]
后面的流程将6作为pivot分左右两侧继续递归就一样了。
这样比只是在最后循环结束后多了一次交换过程。

网上的样例代码如下：

//Java 代码实现
 public class QuickSort implements IArraySort {
 
     @Override
     public int[] sort(int[] sourceArray) throws Exception {
         // 对 arr 进行拷贝，不改变参数内容
         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 
         return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
       }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}