归并排序

  归并排序是一种稳定的排序算法，先进行分组，再进行排序。这个过程中需要采用递归的方法。还需要定义一个辅助数组，用于合并分开的两个子序列。

优点

1、在众多排序算法中，效率可以达到最快，时间复杂度为O（nlogn）
2、由于是稳定排序，故相同的元素会保持排序前的位置，如3，4，4，5，进行排序后，第一个4始终在第二个4前面，适用于某些特定场景。

缺点

  归并算法需要O(n)的辅助空间，而快速排序只需要O(logn)的辅助空间，故该算法的空间复杂度略高。

时间复杂度

始终为O(logn)

空间复杂度

始终为O(n)

代码如下

package cn.tedu;import java.util.Arrays;public class MergeSort1 {public static void mergerSort(boolean flag, int[] a ,int left, int mid, int right){//定义辅助数组int [] t = new int[a.length];int m = left;   //记录第一个序列首编号int n = mid+1;  //记录第二个序列首编号int k = left;while(m<=mid && n<=right){if (flag) {//升序if(a[m]<=a[n]){t[k]=a[m];k++;m++;}else{t[k]=a[n];k++;n++;}}else{//降序if(a[m]>=a[n]){t[k++]=a[m++];  //这种形式与升序中的 t[k]=a[m]; k++; m++;的效果是一样的}else{t[k++]=a[n++];}}}while(m<=mid){   //若第一个序列还有数字，就把数字插入辅助数组后面t[k++]=a[m++];}while(n<=right){t[k++]=a[n++];}//将辅助数组中的元素复制到原数组相应位置while(left < k){a[left]=t[left];left++;}}public static void divide(boolean flag, int[] a, int first, int last){int mid = 0;if (first < last){mid = (first+last)/2;divide(flag, a, first, mid);  //对第一序列进行递归排序divide(flag, a, mid+1,last);  //对第二序列进行递归排序mergerSort(flag, a, first, mid, last);  //进行合并}}public static void main(String[] args) {int[] a1 = {44,33,12,66,45,66,88,99,23};int[] a2 = {66,33,5,2,8,6,999,55,44,16};//进行升序divide(true,a1,0,a1.length-1);//进行降序divide(false,a2,0,a2.length-1);System.out.println("升序："+Arrays.toString(a1));System.out.println("降序："+Arrays.toString(a2));
//        Arrays.stream(a1).forEach(word -> System.out.print(word+"   "));
//        System.out.println();
//        Arrays.stream(a2).forEach(word -> System.out.print(word+"   "));}
}

运行结果