排序算法-快速排序

属性

        快速排序是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
            //现在begin下标相当于已经没有数据了，是一个坑，要通过end下标找到一个比参考值小的值放到这个坑中
            while (begin=tmp){
                end--;
            }
            //跳出了上面的循环说明找到了一个比参考值小的数据
            //将数据放到坑中
            arr[begin]=arr[end];
            //现在end下标相当于已经没有数据了，是一个坑，要通过begin下标找到一个比参考值大的值放到这个坑中
            while (begin
                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 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(rid1){
            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(rid1){
                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;
    }