归并排序(merge-sort)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的答案"修补"在一起,即分而治之).

1. package com.structures.sort; 
2.  
3. blic class MergeSort { 
4.   public static void main(String[] args) { 
5.       int[] arr = new int[80000]; 
6.       for (int i = 0; i < 80000; i++) { 
7.           arr[i] = (int) (Math.random() * 8000000); 
8.       } 
9.       int[] temp = new int[arr.length]; 
10.       long start = System.currentTimeMillis(); 
11.  
12.       mergeSort(arr,0,arr.length-1,temp); 
13.       long end = System.currentTimeMillis(); 
14.       System.out.println("耗时:" + ((end – start)) + "ms"); 
15.       /* 
16.       耗时:15ms 
17.        */ 
18.   } 
19.  
20.   //分+合 
21.   public static void mergeSort(int[] arr, int left, int right, int[] temp) { 
22.       if (left < right) { 
23.           int mid = (left + right) / 2; 
24.           //向左递归进行分解 
25.           mergeSort(arr, left, mid, temp); 
26.           //向右递归进行分解 
27.           mergeSort(arr, mid + 1, right, temp); 
28.           //合并 
29.           merge(arr, left, mid, right, temp); 
30.       } 
31.   } 
32.  
33.   /** 
34.    * 合并 
35.    * @param arr   已排序的原始数组 
36.    * @param left  左边有序序列的初始索引 
37.    * @param mid   中间索引 
38.    * @param right 右边索引 
39.    * @param temp  做中转数组 
40.    */ 
41.   public static void merge(int[] arr, int left, int mid, int right, int[] temp) { 
42.       int i = left;//初始化i,左边有序序列的初始索引 
43.       int j = mid + 1;//初始化j,右边有序序列的初始索引 
44.       int t = 0;//指向temp数组的当前索引 
45.  
46.       //(一) 
47.       //先把左右两边(有序)的数据按照规则填充到temp数组 
48.       //直到左右两边的有序序列,有一边处理完毕为止,即全部填充到temp数组 
49.       while (i <= mid && j <= right) { 
50.           //如果左边的有序序列小于等于右边的有序序列的当前元素 
51.           //即将左边的当前元素拷贝到temp数组 
52.           //然后t++,i++后移 
53.           if (arr[i] <= arr[j]) { 
54.               temp[t] = arr[i]; 
55.               t += 1; 
56.               i += 1; 
57.           } else {//反之,将右边有序序列的当前元素,填充到temp数组 
58.               temp[t] = arr[j]; 
59.               t += 1; 
60.               j += 1; 
61.           } 
62.       } 
63.  
64.       //(二) 
65.       //把有剩余数据的一边的数据依次填充到temp 
66.       while (i <= mid) {//左边的还有剩余,填充到temp数组 
67.           temp[t] = arr[i]; 
68.           t += 1; 
69.           i += 1; 
70.       } 
71.       while (j <= right) { 
72.           temp[t] = arr[j]; 
73.           t += 1; 
74.           j += 1; 
75.       } 
76.  
77.       //(三) 
78.       //将temp数组的元素拷贝到arr 
79.       //注意并不是每次都拷贝所有 
80.       //第一次合并leftTemp = 0,right = 1,第二次合并leftTemp = 2,right = 3,第三次合并leftTemp = 0,right = 3… 
81.       t = 0; 
82.       int leftTemp = left; 
83.       while (leftTemp <= right) { 
84.           arr[leftTemp] = temp[t]; 
85.           leftTemp += 1; 
86.           t += 1; 
87.       } 
88.   }