【排序算法系列 5】 高级排序——归并排序

【排序算法系列 1】冒泡排序 【排序算法系列 2】选择排序 【排序算法系列 3】 插入排序 【排序算法系列 4】 高级排序——希尔排序（插入排序的改进） 【排序算法系列 5】 高级排序——归并排序 【排序算法系列 6】 高级排序——归并排序（由冒泡排序改进） 【排序算法系列 7】堆排序

---

简介

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

需求

排序前：{8,4,5,7,1,3,6,2}排序后：{1,2,3,4,5,5,6,7,8}

归并排序原理

尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。将相邻的两个子组进行合并成一个有序的大组；不断的重复步骤2，直到最终只有一个组为止。

归并原理

归并排序API设计

类名Merge构造方法Merge()：创建Merge对象成员方法 11.public static void sort(Comparable[] a)：对数组内的元素进行排序成员方法 22.private static void sort(Comparable[] a, int lo, int hi)：对数组a中从索引lo到索引hi之间的元素进行排序成员方法 33.private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到所以mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）成员方法 44.private static boolean less(Comparable v,Comparable w):判断v是否小于w成员方法 55.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值成员变量1.private static Comparable[] assist：完成归并操作需要的辅助数组

归并排序的代码实现

public class Merge { //归并所需要的辅助数组 private static Comparable[] assist; //比较v元素是否小于w元素 private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)<0; } //数组元素i和j交换位置 private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } //对数组a中的元素进行排序 public static void sort(Comparable[] a) { //1.初始化辅助数组assist； assist = new Comparable[a.length]; //2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引； int lo=0; int hi=a.length-1; //3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序 sort(a,lo,hi); } //对数组a中从lo到hi的元素进行排序 private static void sort(Comparable[] a, int lo, int hi) { //做安全性校验； if (hi<=lo){ return; } //对lo到hi之间的数据进行分为两个组 int mid = lo+(hi-lo)/2;// 5,9 mid=7 //分别对每一组数据进行排序 sort(a,lo,mid); sort(a,mid+1,hi); //再把两个组中的数据进行归并 merge(a,lo,mid,hi); } //对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并 private static void merge(Comparable[] a, int lo, int mid, int hi) { //定义三个指针 int i=lo; int p1=lo; int p2=mid+1; //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处 while(p1<=mid && p2<=hi){ //比较对应索引处的值 if (less(a[p1],a[p2])){ assist[i++] = a[p1++]; }else{ assist[i++]=a[p2++]; } } //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处 while(p1<=mid){ assist[i++]=a[p1++]; } //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处 while(p2<=hi){ assist[i++]=a[p2++]; } //把辅助数组中的元素拷贝到原数组中 for(int index=lo;index<=hi;index++){ a[index]=assist[index]; } } }

归并排序的时间复杂度: O(nlogn)