排序算法-快速排序

属性

        快速排序是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下标的中间值来作为参考值//获得了中间值的下标tmpIndexint 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;}