数据结构Java版排序（二）

快排需要结合上一节内容进行理解哦 ❀

1.快排的优化

此部分内容紧接上节中文末提及的快排内容

上节中所提及的快排可以是从左边或者右边进行开始找的基准进行排序的

但在日常中，我们很可能遇到部分已经排列规整的数，那么此时我们若用上述方法，则将简单问题复杂化，所以引入了下面所说的随机选取和三数取中法来实现

优化方案①：随机选取（仍是对于基准而言）

问题：当随机选取到该数组序列中最大的数或者最小的数作为基准时出现了单分支的情况。就并改变原先的时间复杂度O(N²），空间复杂度为O(N)的状况。

优化方案②：三数取中法

详述：即利用折半的思想，分别找到两端的数和中间的数，分别比较其中间大小的数来作为基准。可以将基准放于数组开始的位置，这样相当于将其转换成了从左边找

解题思路：

①设置两端的下标分别为start和end，设置中间的下标为mid；数组为array；

②当array[start]<=array[end]时:

a.array[start]>array[mid],此时排列为：mid start end

b.array[start]<array[mid],此时排列为: start mid end

其它：start mid end

③当array[start]>array[end]时:

a.array[end]>array[mid],此时排列为：mid end start

b.array[start]<array[mid],此时排列为: end start mid

其它：end mid start

代码如下：（利用三数取中法完整的快速排序）{递归版本}

  public static void quickSort(int []array){
        quick(array,0,array.length-1);

    }
    public static void quick(int []array,int left,int right){
if(left>=right){
    return ;
}//找到基准之前找到中间值的大小，使用三数取中法
        int midValIndex=findMidValIndex(array,left,right);
swap(midValIndex,left);//交换中间值的大小给left，这样left就成了基准值的位置
//找基准
        int pivot=patition(array,left,right);
//递归左边的
quick(array,left,pivot-1);
//递归右边的
quick(array,pivot+1,right);
    }
    private static int findMidValIndex(int []array,int start,int end){
int mid=start+((end-start)>>>1);//防止栈的溢出
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid]>array[start]){
                return start;
            }else if(array[mid]<array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }
    public static int patition(int []array,int start,int end) {
        int tmp = array[start];
        while (start < end) {
            while (start < end && array[end] >= tmp) {
                end--;
            }//end下标遇到了小于tmp的值
            array[start] = array[end];
            while (start < end && array[start] <= tmp) {
                start++;
            }//start下标遇到了大于tmp的值
            array[end] = array[start];
        }//当start=end时
        array[start]=tmp;
        return start;
    }

优化③： partition 过程中把和基准值相等的数也选择出来（把和基准相同的数据从两边移到跟前来）这样的话中间部分将不用再重新递归，提高了效率

优化④：待排序区间小于一个阈值时（例如 48），使用直接插入排序（当越排序，数据越趋于有序时，来进行优化）

  public static void insertSort2(int[] array,int start,int end) {
        for (int i = 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 {
                    //array[j+1] = tmp;  只要j回退的时候，遇到了 比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了 小于0 的地方
            array[j+1] = tmp;
        }

    }

    //快速排序
    public static void quickSort(int []array){
        quick(array,0,array.length-1);

    }
    public static void quick(int []array,int left,int right){
if(left>=right){
    return ;
}if(right-left+1<=30){
    //使用直接插入排序
            insertSort2(array,left,right);
    return;
        }
//找到基准之前找到中间值的大小，使用三数取中法
        int midValIndex=findMidValIndex(array,left,right);
swap(midValIndex,left);//交换中间值的大小给left，这样left就成了基准值的位置
//找基准
        int pivot=patition(array,left,right);
//递归左边的
quick(array,left,pivot-1);
//递归右边的
quick(array,pivot+1,right);
    }
    private static int findMidValIndex(int []array,int start,int end){
int mid=start+((end-start)>>>1);//防止栈的溢出
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid]>array[start]){
                return start;
            }else if(array[mid]<array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }
    public static int patition(int []array,int start,int end) {
        int tmp = array[start];
        while (start < end) {
            while (start < end && array[end] >= tmp) {
                end--;
            }//end下标遇到了小于tmp的值
            array[start] = array[end];
            while (start < end && array[start] <= tmp) {
                start++;
            }//start下标遇到了大于tmp的值
            array[end] = array[start];
        }//当start=end时
        array[start]=tmp;
        return start;
    }

利用三数取中法完整的快速排序{非递归版本}

解题思路：（借助栈来进行完成）

①找基准：划分基准之后，将左右数对都放到栈中；前提：基准pivot左边有两个元素（pivot>left+1），右边有两个元素(pivot<right-1);

②借助栈来解决问题：分别入以基准为界限的边界进行入栈，边界左右两边均要进行入栈。然后直到两端有序为1，不能入栈为止。出栈到栈为空为止。（注意入栈的是下标）

代码如下：

    public static void quickSort1(int []array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=patition(array,left,right);
if(pivot>left+1){
    //左边有两个元素
    stack.push(left);
    stack.push(pivot-1);
}
if(pivot<right-1){
    stack.push(pivot+1);
    stack.push(right);
}
while(!stack.isEmpty()){
    right=stack.pop();
    left=stack.pop();
     pivot=patition(array,left,right);
    if(pivot>left+1){
        //左边有两个元素
        stack.push(left);
        stack.push(pivot-1);
    }
    if(pivot<right-1){
        stack.push(pivot+1);
        stack.push(right);
    }
}
    }

2.归并排序

①原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

引入：将两个有序的数组合并成一个数组的问题。

代码如下：

 //两个有序表的归并
    public static  int [] mergeArray(int[]array1,int[]array2){
        int s1=0;
        int e1=array1.length-1;
        int s2=0;
        int e2=array2.length-1;
        int index=0;
        int []tmp=new int[array1.length+array2.length];
        while (s1 <= e1 && s2 <= e2) {
            if(array1[s1] <= array2[s2]) {
                tmp[index] = array1[s1];
                index++;
                s1++;
            }else {
                tmp[index] = array2[s2];
                index++;
                s2++;
            }
        }
//此时表示s2数组已经走完，把剩下的s1数组中的数依次放入合并的数组中即可
        while (s1 <= e1) {
            tmp[index++] = array1[s1++];
            //此处也可以像上面那样写成index++；s1++;
        }
//此时表示s1数组已经走完，把剩下的s2数组中的数依次放入合并的数组中即可
        while (s2 <= e2) {
            tmp[index++] = array2[s2++];
        }
        return tmp;
    }

归并排序：（递归版）

解题思路：

利用了二叉树递归的思想来解题

①利用折半查找找到中间mid值，由此对根root,进行分支，进行递归的操作

②循环上述操作，直到单支只剩一个元素时，将两个单支元素按顺序合并在一起，直至到与根对应的位置

代码如下：

//归并排序
 public static void mergeSort1(int[] array) {
        mergeSortInternal(array,0,array.length-1);
    }

    private static void mergeSortInternal(int[] array,int low,int high) {
        if(low>=high) {
            return;
        }
        //为了避免栈的溢出的写法
        int mid = low + ((high-low) >>> 1);
        //左边递归
        mergeSortInternal(array,low,mid);
        //右边递归
        mergeSortInternal(array,mid+1,high);
        //合并
        merge(array,low,mid,high);
    }
//上面开始合并数组奠定了基础
    private static void merge(int[] array,int low,int mid,int high) {
        int[] tmp = new int[high-low+1];
        int k = 0;
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 =  high;
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }

        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }

        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //复制tmp数组的元素 放入原来的数组array中
        for (int i = 0; i < k; i++) {
            array[i+low] = tmp[i];
        }
    }

 

归并排序：（非递归版）

解题思路：

利用将数组如树进行拆开后，回到原来的模样，由1个单独的数据，变成2个有序的数据，变成4个有序的数据，直至当它变成与原待排序列等长的数据为止

代码如下：

  public static void mergeSort(int[] array) {
        int nums = 1;//单个数据的时候
        while (nums < array.length) {
            //数组每次都要进行遍历,确定要归并的区间
            for (int i = 0; i < array.length; i += nums*2) {
                int left = i;
                int mid = left+nums-1;
                //防止mid的越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+nums;
                //防止right的越界
                if(right >= array.length) {
                    right = array.length-1;
                }
                //小标确定之后，进行合并
                merge(array,left,mid,right);
            }
            nums *= 2;
        }
    }

②性能分析

时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定

3.七大排序总结

4.其余非基于比较的排序（大家基于了解的层面）

①计数排序

计数排序 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/26595385?group_id=842495057868226560

②基数排序

1.10 基数排序 | 菜鸟教程 (runoob.com)https://www.runoob.com/w3cnote/radix-sort.html

③桶排序

桶排序（最快最简单的排序） - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/33905160感谢观看~