归并排序
归并排序主要分成两部分实现，分、合两部分，分是把数组分成两半，再递归的对子数组进行 分 操作，直到分成一个个单独的数。合是把两个数组合并为有序数组，在对有序数组进行合并，直到全部子数组合并为一个完整的数组。
算法原理
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤c直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
动图演示
代码实现
public class MergeSort { //归并所需的辅助数组 private static Comparable[] assist; //比较 v 是否小于 w public static boolean less(Comparable v,Comparable w){ return v.compareTo(w) < 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } //排序 public static void sort(Comparable[] a){ //初始化辅助数组 assist = new Comparable[a.length]; int l = 0; int h = a.length - 1; sort(a,l,h); } private static void sort(Comparable[] a,int l,int h){ if (h <= l){ return; } //分组 int mid = l +(h - l) / 2; //分别对每组数据排序 sort(a,l,mid); sort(a,mid + 1,h); //对数组进行归并 merge(a,l,mid,h); } //对数组进行归并 private static void merge(Comparable[] a,int l,int mid,int h){ //定义三个指针 int i = l; int p1 = l; int p2 = mid + 1; //遍历，移动p1,p2指针，比较两处索引的值,小的放到辅助数组的对应索引处 while (p1 <= mid && p2 <=h){ 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 <= h){ assist[i++] = a[p2++]; } //把辅助数组中的元素拷贝到原数组中 for (int j = l; j <= h; j++) { a[j] = assist[j]; } } }
public class MergeSortTest { public static void main(String[] args) { Integer[] arr = {5,6,3,1,8,7,2,4}; MergeSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前：{5,6,3,1,8,7,2,4} //排序后：{1,2,3,4,5,6,7,8}
复杂度
时间复杂度：O(nlogn)
空间复杂度：O(n)
