一、快速排序

整体过程：
1.先从数组中找一个数作为基准数，
2 进行分区，分区时大于这个数得全部放到右边，小于这个数得全部放到左边，等于这个数得全部放到中间（核心过程）
3再通过递归再更小得范围执行2步骤，直到递归到只有一个数

思路解析
比如针对 3 4 2 1 5 6 0 3
它的一个思路是首先有一个左边区域和右边区域，

左边区域的最靠右的起始下标为-1，右边区域的最靠左的起始下标为length-1

然后以数组最后一个数3为界限，大于这个数的都在右边，小于这个数的都在左边

首先排的时候index 为0，然后判断下标为0的数3 ==3，所以左右边界不动，index继续++
当index为1，判断下标为1的数4 4>3 ,所以右边界往右移动一位到length-2 值为0 将值为0与值为4调换位置 ======> 3 0 2 1 5 6 4 3
然后继续判断index为1 此时值为 0 0<3 所以左边界加1到0，值为3，将3与0调换位置，然后index+1 到2 ======> 0 3 2 1 5 6 4 3

当index为2时，判断下标为2的数 2<3, 所以左边界加1到1, 值为3 将 3与2
调换位置，然后index+1 到3 ======> 0 2 3 1 5 6 4 3
当index为3时，判断下标为3的数 1<3, 所以左边界加1到2 值为3 将3与1调换位置 然后index+1 到4 ======> 0 2 1 3 5 6 4 3

当index为4时，判断下标为4的数 5>3, 所以右边界往右移动一位到length-3 值为6，将值为6与值5调换位置 ======> 0 2 1 3 6 5 4 3
当index为4时，判断下标为4的数 6>3, 所以右边界往后移动一位到length-4----即下标为4，但是此这样就不满足index<右边界 所以跳出来
跳出来后将index为4的值和数组的最后一个值做交换 ===》 0 2 1 3 3 5 4 6
即结束

代码实现

public static void quickSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {if (L >= R) {return;}int[] equalE = partition(arr, L, R);process(arr, L, equalE[0] - 1);process(arr, equalE[1] + 1, R);
}// arr[L...R]范围上，拿arr[R]做划分值，
// L....R < = >
public static int[] partition(int[] arr, int L, int R) {int lessR = L - 1;int moreL = R;int index = L;while (index < moreL) {if (arr[index] < arr[R]) {lessR++;swap(arr, lessR, index);index++;} else if (arr[index] > arr[R]) {moreL--;swap(arr, moreL, index);} else {index++;}}swap(arr, moreL, R);//比如342555578 //返回3，6return new int[] { lessR + 1, moreL };  
}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}

但是我们现在实现的代码整体时间复杂度为O（n^2); ->因为当数据为[0,1,2,3,4,5]==>这种情况时间复杂度是O(N^2)
所以其实是可以进行优化处理的
如何优化呢？即随机选择了一个划分值放到了最右边
整体的代码量比上面多出一行
因为是随机选择得划分值，那么打到任意一个位置，选取作为划分值得权重是一样得
这样一来根据数学推算，最后收敛于O(NlogN)

public static void quickSort3(int[] arr) {if (arr == null || arr.length < 2) {return;}process3(arr, 0, arr.length - 1);}public static void process3(int[] arr, int L, int R) {if (L >= R) {return;}swap(arr, L + (int) (Math.random() * (R - L + 1)), R);int[] equalArea = partition(arr, L, R);process3(arr, L, equalArea[0] - 1);process3(arr, equalArea[1] + 1, R);}
// arr[L...R]范围上，拿arr[R]做划分值，
// L....R < = >
public static int[] partition(int[] arr, int L, int R) {int lessR = L - 1;int moreL = R;int index = L;while (index < moreL) {if (arr[index] < arr[R]) {lessR++;swap(arr, lessR, index);index++;} else if (arr[index] > arr[R]) {moreL--;swap(arr, moreL, index);} else {index++;}}swap(arr, moreL, R);//比如342555578 //返回3，6return new int[] { lessR + 1, moreL };  
}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}

关键点：
把核心过程定义出来，然后左右边界求出来，之后通过递归不断的遍历下去，
就是再更小的范围上求出划分值对应得左右边界