2021新年算法小专题—3.大话排序算法下-归并排序快速排序（Java）

本文链接：https://blog.csdn.net/weixin_43604162/article/details/113963313

接第一篇大话排序算法上。本文介绍归并、快排两种排序算法。

更多文章：

新年算法小专题1.滑动窗口（Java）
新年算法小专题1.滑动窗口刷题（Java）
新年算法小专题2.股票买卖（Java）
新年算法小专题2.股票买卖刷题（Java）

高级排序—归并排序

概述

归并排序是建立在归并操作上的一种排序算法，也是分治法的一个典型应用。它把完整的序列分割成多个很小的子序列，在子序列内部进行排序，然后将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

在归并排序算法中我们一般使用递归去处理。使用二分的分治方法，把数组分成left、right两段，然后递归继续二分，直到数组长度小于2。同时把分割后逐层返回的数组进行两两组合（逐层排序）。归纳如下：

把长度为n的数组分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

参考代码

    public static int[] MergeSort(int[] array) {

        if (array.length < 2) // 待排序数组长度小于2直接返回
            return array;
        int mid = array.length / 2;// 将数组分成两半，[0,mid) [mid.length)
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));// 递归排序

    }

    // 将两段排序好的数组【合并】成一个排序数组
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];// 合并后的数组

        // index-新数组下标 i-left数组下标 j-right数组下标
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)// left数组到头了 使用right数组的值
                result[index] = right[j++];
            else if (j >= right.length)// right数组到头了 使用left数组的值
                result[index] = left[i++];
            else if (left[i] > right[j])// 谁小就先放谁
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }

高级排序—快速排序

概述

快速排序也是分治的思想实现的。通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

它把一个串（list）分为两个子串（sub-lists）。具体描述如下：

从数组中挑出一个元素，称为基准（pivot），这里取数组的最后一个元素；
根据基准分组。以基准元素对数组重新排序，使用一个指针i表示基准元素欲插入的位置，在循环中使用j遍历范围内所有元素，当找到小于等于基准元素的元素时就把它与i的下一个位置进行交换（j与++i进行交换）。通过这样的操作，最后能将基准元素放在一个位置，把该范围的数组元素分割成两部分，使其左边都是小于等于基准元素的值，右边都是大于基准元素的值。
递归地在每个部分中重复上面的步骤。小于基准值元素的子序列和大于等于基准值元素的子序列进行如上的排序。

参考代码

    public static void quickSort(int[] a, int low, int high) {
        if(low<high && low>=0 && high<a.length){
             int p=partition1(a,low,high);// 基准位置下标

            quickSort(a,low,p-1);
            quickSort(a,p+1,high);
        }
    }
    public static int partition(int []a,int low,int high){
        int pivot =a[high];// 基准
        int i=low-1;// 初始化一个【比基准小的元素】的下标,实际就要做基准的新位置
        for(int j=low;j<=high;j++){
            if(a[j]<=pivot){// 如果当前元素小于基准
                int tmp=a[++i];//交换a[i]和a[j]
                a[i]=a[j];
                a[j]=tmp;
            }
        }
        return i;
    }

快速排序事实上有许多不同的实现方式。因为快速排序的思想是选出一个基准，然后按照某种方式分区，使基准左侧的元素都小于基准、右侧的元素都大于基准，然后再次递归处理这两个部分。也就是说，分区（partition）是可以有不同的实现方式的，只要能实现上述要求，如何实现都可以。下面介绍另一种不同的分区方式。

前面我们是使用指针i、和循环中的下标j进行比较交换，最后i指向的下一个位置就是基准的位置。我们也可以使用两个指针i、j分别从最左边和最右边向中间移动，当i遇到比基准大的值时交换i和基准元素，并更新基准下标为i；当j遇到比基准小的值时交换j和基准元素，同时更新基准下标为j。总之，就是为了把基准元素放在中间，使左边都比它小，右边都比它大。参考代码如下：

（基准仍然取最后一个元素。使用一个dir变量来指示是向左还是向右移动，初始时为true代表向右移动，即i++，当发生过一次交换后就调转方向，换成另一个方向去移动。最终i、j两个指针相遇，说明移动完毕。）

public static int partition1(int []a,int low,int high){
        
        int i=0,j=high,p=high;// i左边滑动，j右边滑动，p是基准位置
        boolean dir=true;// 代表right移动 i++
        while (i!=j){
            if(dir){
                if(a[i]>a[p]){
                    int tmp=a[i];
                    a[i]=a[p];
                    a[p]=tmp;
                    p=i;
                    dir=false;
                }else
                    i++;
            }else {
                if(a[j]<a[p]){
                    int tmp=a[j];
                    a[j]=a[p];
                    a[p]=tmp;
                    p=j;
                    dir=true;
                }else
                    j--;
            }
        }
        return p;
    }