排序算法（2）快排

交换排序

思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

一、冒泡排序

 public static void BubbleSort(int[] array){
        boolean flg = false;
        for(int i = 0;i<array.length-1;i++){
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                break;
            }
        }
    }

总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

二、快速排序

基本思想：基于分治法的算法。任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1、Hoare法

//快排，递归,Hoare法
    //时间复杂度最坏下O(N^2)
    //快排一般说均匀分割下复杂度优化后趋于n*logn
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start>=end){
            return;
        }
        int par = partition(array,start,end);
        quick(array,start,par-1);
        quick(array,par+1,end);
    }
    private static int partition(int[] array,int left,int right){
        int i = left;
        int pivot = array[left];
        while(left<right){
            while(left<right && array[right]>=pivot){
                right--;
            }
            while(left<right && array[left]<=pivot){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);

        return left;
    }

时间复杂度：最坏情况下O(N^2)，如果是均匀分割下复杂度优化后趋于n*logn，快排一般用于乱序

问题：

1、堆和快排都是n*logn，那么那个更快呢？

快排还是更快一些，因为时间复杂度是粗略估计的，实际上堆排是kn*logn，最后都把k给去掉了，快排有可能是2logn，堆排是3logn。

2、与基准值比较的时候可以不写‘=’吗？

不可以！！！

3、为什么从右边开始？

如果先走左边导致最后相遇的地方是比基准大的数据，交换完后，会把大的放到了前面，不满足快排思想。

注意：因为快排是递归，数据太多的情况下会导致溢出

2、挖坑法

 private static int partition2(int[] array,int left,int right){
       int tmp = array[left];
       while(left<right){
           while(left<right&&array[right]>=tmp){
               right--;
           }
           array[left] = array[right];
           while(left<right&&array[left]<=tmp){
               left++;
           }
           array[right] = array[left];
       }
       array[left] = tmp;
       return left;
    }

3、双指针法（了解）

 private static int partition3(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                 swap(array,cur,prev);
            }
                cur++;
        }
        swap(array,prev,left);
        return prev;
    }

4、快速排序优化（减小递归次数）

1. 三数取中法选key

2. 递归到小的子区间时，可以考虑使用插入排序

趋于有序的情况下，插入排序效率最高，并且可以减少递归次数

   private static void quick(int[] array,int start,int end) {
        if(start>=end){
            return;
        }
        if(end-start+1<=5){
            insertSortRange(array,start,end);
            return;
        }
        
        int index = midTreeNum(array,start,end);
        swap(array,index,start);
        
        int par = partition(array,start,end);
        quick(array,start,par-1);
        quick(array,par+1,end);
    }
    public static void insertSortRange(int[] array,int start,int end){
        for(int i = start+1;i<=end;i++){
            int tmp = array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int partition(int[] array,int left,int right){
        int i = left;
        int tmp = array[left];
        while(left<right){
            while(left<right && array[right]>=tmp){
                right--;
            }
            while(left<right && array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);

        return left;
    }
    private static int midTreeNum(int[] array,int left,int right){
        int mid = (left+right)/2;
        //返回的是中位数的下标
        if(array[left]<array[right]){
            if (array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if (array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

5、快排非递归

使用栈

    void quickSortNonR(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int par = partition(array,left,right);
        if(par>left+1){
            //如果左数只有一个值则不需要排序
            //先放左再放右
            stack.push(left);
            stack.push(par-1);
        }
        if(par<right-1){
            //先放左再放右
            stack.push(par+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            //先取出来的是右之后是左
            right = stack.pop();
            left = stack.pop();
            par = partition(array,left,right);
            //重复最初的操作
            if(par>left+1){
                //如果左数只有一个值则不需要排序
                stack.push(left);
                stack.push(par-1);
            }
            if(par<right-1){
                stack.push(par+1);
                stack.push(right);
            }
        }
    }