选择排序的升级版本归并排序， 归并排序有二路归并，三路归并和多路归并，我这次只分析下二路归并，有机会在分析下别的。
归并排序的思想是这样的：
设数组a中存放了n个数据元素，初始时我们把它们看成是n个长度为1的有序子数组，然后从第一个子数组开始，把相临的子数组两两合并，得到n/2个（若n/2为小数则上取整）长度为2的新的有序子数组（当n为奇数时最后一个新的有序子数组的长度为1）；对这些新的有序子数组再两两归并；如此重复，直到得到一个长度为n的有序数组为止。多于二路的归并排序方法和二路归并排序方法类同。
步骤：
1、首先是将数组分开， 应用递归的方式， 简单暴力；
2、然后对数组进行两辆归并（就是合并为一个数组的过程）；
3、第二步的过程中需要创建一个新的数组，对改变顺序后的原数组的部分进行保存；‘
//也许代码是说明问题的最好方法， 代码中已经做了注释
package merge;
public class MergeSort {
// 接收传来的参数 对数组进行拆分
public int[] sort(int[] array, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
sort(array, low, middle);
sort(array, middle + 1, high);
// 进行排序和合并
merge(array, low, middle, high);
}
return array;
}
// 进行排序和合并
public void merge(int[] array, int low, int middle, int high) {
// 创建一个临时数组
int cLow = low;
int[] tempArray = new int[array.length];
// 定义临时数组及参数数组下标如下：
int tempIndex = low;
int right = middle + 1;
while(low <= middle && right <= high){
if(array[low] < array[right]){
tempArray[tempIndex++] = array[low++];
}else{
tempArray[tempIndex++] = array[right++];
}
}
//如果条件满足的话，对middle前面的还没有存入的直接放入tempArray，因为middle后面的已经没有了
while(low <= middle){
tempArray[tempIndex++] = array[low++];
}
//原理和上面的相同
while(right <= high){
tempArray[tempIndex++] = array[right++];
}
//将排序后的 部分数组 重新放入原数组
for(int i = cLow; i <= high; i++){
array[i] = tempArray[i];
}
}
}
测试类如下：
package Test;
import merge.MergeSort;;
public class Test {
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int[] array = createArray();
long ct1 = System.currentTimeMillis();
int[] arrays = mergeSort.sort(array, 0, array.length - 1);
long ct2 = System.currentTimeMillis();
display(arrays);
System.out.println("所消耗的时间：" + (ct2 - ct1) + " ms");
}
public static void display(int[] arrays) {
System.out.println("排序后数据：");
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i] + "\t");
if ((i + 1) % 10 == 0) {
System.out.println();
}
}
System.out.println();
}
public static int[] createArray() {
int[] array = new int[100000];
System.out.println("数组中元素是：");
for (int i = 0; i < 100000; i++) {
array[i] = (int) (Math.random() * 1000);
System.out.print(array[i] + "\t");
if ((i + 1) % 10 == 0) {
System.out.println();
}
}
System.out.println();
return array;
}
}
归并排序对 100000个数进行排序的时间大约是 4300ms ， 可见比快排的效率低了很多。
时间复杂度的分析：
归并排序的总的时间复杂度为O(nlog2 n)。
归并排序需要的附加存储空间为O(n)，所需辅助空间较大。
二路归并排序是稳定的。