属性
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
. 1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
代码及注释（递归写法）
public static void quickSort(int[]arr){
quick1(arr,0,arr.length-1);
}
private static void quick(int[]arr,int begin,int end){
//出递归
if(begin>=end){
return;
}
//由于参考值的取值要尽量取数据的中间值，所以我们可以拿begin，end和mid下标的中间值来作为参考值
//获得了中间值的下标tmpIndex
int tmpIndex=threeMid(arr,begin,end);
//将中间值交换到第一个位置作为参考值
swap(arr,begin,tmpIndex);
//进行数据的划分，将小于参考值的数据放到左边，大于参考值的数据放到右边
//得到划分好数据后，参考值最终放到的位置（参考值排序后的下标）
int rid=parttion1(arr,begin,end);
//以同样的方式划分参考值左边和右边的数据
quick(arr,begin,rid-1);
quick(arr,rid+1,end);
}
//进行begin-end范围内数据的划分，将小于参考值的数据放到左边，大于参考值的数据放到右边
private static int parttion1(int[]arr,int begin,int end){
//用挖坑法进行划分
int tmp=arr[begin];
while (begin<end){
//现在begin下标相当于已经没有数据了，是一个坑，要通过end下标找到一个比参考值小的值放到这个坑中
while (begin<end&&arr[end]>=tmp){
end--;
}
//跳出了上面的循环说明找到了一个比参考值小的数据
//将数据放到坑中
arr[begin]=arr[end];
//现在end下标相当于已经没有数据了，是一个坑，要通过begin下标找到一个比参考值大的值放到这个坑中
while (begin<end&&arr[begin]<=tmp){
begin++;
}
//跳出了上面的循环说明找到了一个比参考值大的数据
//将数据放到坑中
arr[end]=arr[begin];
}
//当begin和end指向一个下标时便退出了循环，而他们指向的这个下标是一个坑（没有数据）
//将参考值放到这个坑中
arr[begin]=tmp;
//返回参考值所在的下标，方便去划分参考值左边和右边的数据
return begin;
}
//在array数组中找到下标begin，mid，end的中间值
private static int threeMid(int[] array,int begin,int end){
int mid=(begin+end)/2;
if(array[begin]>array[end]){
if(array[end]>array[mid]){
return end;
}
else if(array[mid]>array[begin]){
return begin;
}
else {
return mid;
}
}
else {
if (array[mid]>array[end]){
return end;
} else if (array[begin]>array[end]) {
return begin;
}
else {
return mid;
}
}
}
private static void swap(int[] array,int m,int n){
int tmp=array[m];
array[m]=array[n];
array[n]=tmp;
}
代码及注释（非递归写法）
其实非递归写法的思路和递归相同，只是非递归要自己创建一个栈来模拟出递归的效果而已
//非递归实现快速排序
public static void quickSortNoRrcur(int[] array) {
//当排序的数目小于一定范围时直接用插入排序
if(array.length<5){
InsertSort insertSort=new InsertSort();
insertSort.insertSort(array);
return;
}
Stack<Integer> stack=new Stack<>();
int start=0;
int end=array.length-1;
//三数取中
int midIndex=threeMid(array, start, end);
//把三个数中位于中间的值放到第一位
swap(array,start,midIndex);
//挖坑法将比array[begin]小的放左边，大的放右边
int rid=parttion(array, start, end);
//判断是否满足入栈条件
if(rid>start+1){
stack.push(start);
stack.push(rid-1);
}
if(rid<end-1){
stack.push(rid+1);
stack.push(end);
}
while (!stack.empty()){
end=stack.pop();
start=stack.pop();
//当排序的数目小于一定范围时直接用插入排序
if(end-start+1<5){
InsertSort insertSort=new InsertSort();
insertSort.insertSort(array);
return;
}
//三数取中
midIndex=threeMid(array, start, end);
//把三个数中位于中间的值放到第一位
swap(array,start,midIndex);
//挖坑法将比array[begin]小的放左边，大的放右边
rid=parttion(array, start, end);
//判断是否满足入栈条件
if(rid>start+1){
stack.push(start);
stack.push(rid-1);
}
if(rid<end-1){
stack.push(rid+1);
stack.push(end);
}
}
}
private static int threeMid(int[] array,int begin,int end){
int mid=(begin+end)/2;
if(array[begin]>array[end]){
if(array[end]>array[mid]){
return end;
}
else if(array[mid]>array[begin]){
return begin;
}
else {
return mid;
}
}
else {
if (array[mid]>array[end]){
return end;
} else if (array[begin]>array[end]) {
return begin;
}
else {
return mid;
}
}
}
private static void swap(int[] array,int m,int n){
int tmp=array[m];
array[m]=array[n];
array[n]=tmp;
}
