最近在撸快排，发现网上写的千篇一律，理论定义的步骤和代码稍有些区别，所以按我自己理解的在整理一遍
首先抄一下网上的定义和模拟图：
- 从数列中挑出一个元素，称为 “基准”（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;
}
}
