合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
算法基本思想：
- 首先将未排序的数组，进行拆分成n个单一的数据。
- 然后将这n个数据按照索引顺序，两两组合、排序。（例如：有8个数据，那么第一个和第二个组合，第三个和第四个组合。。。如有未组合的数据这放任其暂时不管）
- 将上面已经两两组合、排序好的数据看成是一个“元素”，再进行两两组合、排序。。。
- 重复上述的步骤，最后就得到已经排序好的数组。
示意图
代码实现：
import java.util.Arrays;
import java.util.Date;
/**
* Created by noonbiteun
* Date: 2017/8/1
*/
public class MergeSort {
private static void merge(int[] unsortArr, int frontIndex, int backIndex, int lastIndex, int[] sortArr) {
int i = frontIndex;//前半段的起始索引
int j = backIndex;//后半段的起始索引
int k = 0;
//合并两个小分组
while (i < backIndex && j < lastIndex) {
if (unsortArr[i] < unsortArr[j]) {
sortArr[k++] = unsortArr[i++];
} else {
sortArr[k++] = unsortArr[j++];
}
}
while (i < backIndex) {
//前半段还有数据
sortArr[k++] = unsortArr[i++];
}
while (j < lastIndex) {
//后半段还有数据
sortArr[k++] = unsortArr[j++];
}
for (int l = 0; l < k; l++) {
//将排序好的数放回
unsortArr[frontIndex + l] = sortArr[l];
}
}
public static void sort(int[] arr, int first, int last, int[] sorted) {
if (first < last - 1) {
int back = (first + last) / 2;
sort(arr, first, back, sorted);
sort(arr, back, last, sorted);
merge(arr, first, back, last, sorted);
}
}
public static void main(String[] args) {
int[] arr = new int[10];
//初始化数组
for (int i = 0; i < 10; i++) {
arr[i] = (int) (Math.random() * (100 + 1));
}
long t1 = new Date().getTime();
System.out.println("原始的顺序： "+ Arrays.toString(arr));
MergeSort.sort(arr, 0, arr.length, new int[arr.length]);
long t2 = new Date().getTime();
System.out.println("排序后顺序： "+ Arrays.toString(arr));
System.out.println("耗时："+(t2-t1)+" ms");
}
}
输出结果：
运行结果
分析小结：
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
