🟡前言
今天是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)
🟡归并排序缺点
要开辟一个新空间，使得空间复杂度提高，典型的 以时间换空间
🟡结语
归并排序利用了分治思想和递归的思路，所以要先掌握这两个知识点才能掌握这种算法
