算法排序5——归并排序&分治思想

2023-01-09 107

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法排序5——归并排序&分治思想

🟡前言

今天是21天挑战赛第二周，本文主要讲归并排序，也是分治思想的重要体现

🟡概述

1️⃣原理图

2️⃣排序原理&思想体现

归并排序就是将数组尽可能拆成等分的两组，直至变成单个元素（分）

然后对拆分出来的元素两两排序后组合，变成一个有序的数组（治）

🟡调用API解决

1️⃣成员变量

private static Comparable[] assist：完成归并操作所需要的辅助数组

2️⃣构造方法和成员方法

构造方法

Merge();

成员方法

public static void sort(Comparable[]a)：对数组a中元素进行排序
public static void sort(Comparable[]a, int lo, int hi)：对数组a中从索引lo到索引hi之间元素进行排序
public static void merge(Comparable[]a, int lo, int mid,int hi)：数组a中从从索引 lo 到索引 min 为一个子数组，从索引 min+1 到索引 hi 为另一个子数组，把a中的两个子数组合并成一个大数组
public static boolean less(Comparable x, Comparable y)：判断x是否小于y
public static void exch(Comparable[]a, int i, int j)：交换数组a中下标为 i 和 j 的元素

3️⃣解题思路

1.定义并初始化一个辅助数组，来完成归并操作

2.定义并初始化数组的最小索引 lo 和最大索引 hi

3.调用一个方法对数组内元素进行排序后归并排序

4️⃣归并排序思路

1.定义三个"指针"p1、p2和 i，用来指向第一子数组的元素、第二子数组的元素和辅助数组的元素

2.比较p1和p2指向元素的大小，将较小的放入辅助数组中

3.将刚才较小元素的索引值和辅助数组索引值都加1，

4.将指针指向新的元素值与另一个子数组内指针指向元素比较，并将较小的元素存放到辅助数组内

5.重复2-4的步骤，直至其中一个指针指向该子数组的最后一个元素为止

6.当其中一个指针走完时，直接将另一个子数组中元素放入辅助数组中

7.将排序完成的元素放回元素组中

5️⃣归并排序代码实现

//定义一个归并排序的含参方法
public static void merge(Comparable[]a, int lo, int mid,int hi){
        int p1 = lo;//定义并初始化一个子数组的索引
        int p2 = mid + 1;//定义并初始化另一个子数组的索引
        int i = lo;//定义并初始化辅助数组的索引
        //当两个索引值都在索引范围内，将数值更小的元素放入辅助数组
        while (p1 <= mid && p2 <= hi){
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }
            else {
                assist[i++] = a[p2++];
            }
        }
        //当p2索引值超出索引范围时（即满足p1没有超出索引范围）
        while (p1 <= mid){
            assist[i++] = a[p1++];//将p1索引所对应剩下的元素复制到辅助数组中
        }
        //当p1索引值超出索引范围时（即满足p2没有超出索引范围）
        while (p2 <= hi){
            assist[i++] = a[p2++];//将p2索引所对应剩下的元素复制到辅助数组中
        }
        //将已排序的辅助数组赋值给原数组
        for(int index = lo; index <= hi; index++){
            a[index] = assist[index];
        }
    }

6️⃣完整代码

public class MergeSort {
    private static  Comparable[] assist;
    public static void sort(Comparable[] a){
        assist = new Comparable[a.length];
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);//归并排序
    }
    public static void sort(Comparable[]a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        int mid = lo + (hi-lo)/2;
        sort(a, lo, mid);//子数组排序
        sort(a, mid+1, hi);//子数组排序
        merge(a, lo, mid, hi);//合成有序的一个大数组
    }
    public static void merge(Comparable[]a, int lo, int mid,int hi){
        int p1 = lo;//定义并初始化一个子数组的索引
        int p2 = mid + 1;//定义并初始化另一个子数组的索引
        int i = lo;//定义并初始化辅助数组的索引
        //当两个索引值都在索引范围内，将数值更小的元素放入辅助数组
        while (p1 <= mid && p2 <= hi){
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }
            else {
                assist[i++] = a[p2++];
            }
        }
        //当p2索引值超出索引范围时（即满足p1没有超出索引范围）
        while (p1 <= mid){
            assist[i++] = a[p1++];//将p1索引所对应剩下的元素复制到辅助数组中
        }
        //当p1索引值超出索引范围时（即满足p2没有超出索引范围）
        while (p2 <= hi){
            assist[i++] = a[p2++];//将p2索引所对应剩下的元素复制到辅助数组中
        }
        //将已排序的辅助数组赋值给原数组
        for(int index = lo; index <= hi; index++){
            a[index] = assist[index];
        }
    }
    public static boolean less(Comparable x, Comparable y){
        return x.compareTo(y) < 0;
    }
}

🟡空间复杂度

总共分为log8（底数为2）层，即log2(n)

每一层都有2^k个元素（8，4，2）

每个子数组的长度：2^（3-k）（0，2，4）

归并最多需要次数：2^（3-k）

每层归并需要的次数：每一层元素个数*每个子数组的长度：23 =8

总次数：层数 * 每层归并需要的次数：3 * 23 ，即log2(n) * 2log2(n) = log2(n) * n

所以时间复杂度为：O(nlogn)

🟡归并排序缺点

要开辟一个新空间，使得空间复杂度提高，典型的以时间换空间

🟡结语

归并排序利用了分治思想和递归的思路，所以要先掌握这两个知识点才能掌握这种算法