归并排序的JAVA实现

转自：http://blog.csdn.net/chenjin_zhong/article/details/6045659

——————————————————————————————————————————————

1. public class MergeSort {  
2.     /** 
3.      * 归并排序 
4.      * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 
5.      * 时间复杂度为O(nlogn) 
6.      * 稳定排序方式 
7.      * @param nums 待排序数组 
8.      * @return 输出有序数组 
9.      */  
10.     public static int[] sort(int[] nums, int low, int high) {  
11.         int mid = (low + high) / 2;  
12.         if (low < high) {  
13.             // 左边  
14.             sort(nums, low, mid);  
15.             // 右边  
16.             sort(nums, mid + 1, high);  
17.             // 左右归并  
18.             merge(nums, low, mid, high);  
19.         }  
20.         return nums;  
21.     }  
22.   
23.     public static void merge(int[] nums, int low, int mid, int high) {  
24.         int[] temp = new int[high - low + 1];  
25.         int i = low;// 左指针  
26.         int j = mid + 1;// 右指针  
27.         int k = 0;  
28.   
29.         // 把较小的数先移到新数组中  
30.         while (i <= mid && j <= high) {  
31.             if (nums[i] < nums[j]) {  
32.                 temp[k++] = nums[i++];  
33.             } else {  
34.                 temp[k++] = nums[j++];  
35.             }  
36.         }  
37.   
38.         // 把左边剩余的数移入数组  
39.         while (i <= mid) {  
40.             temp[k++] = nums[i++];  
41.         }  
42.   
43.         // 把右边边剩余的数移入数组  
44.         while (j <= high) {  
45.             temp[k++] = nums[j++];  
46.         }  
47.   
48.         // 把新数组中的数覆盖nums数组  
49.         for (int k2 = 0; k2 < temp.length; k2++) {  
50.             nums[k2 + low] = temp[k2];  
51.         }  
52.     }  
53.   
54.       
55.     // 归并排序的实现  
56.     public static void main(String[] args) {  
57.   
58.         int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  
59.   
60.         MergeSort.sort(nums, 0, nums.length-1);  
61.         System.out.println(Arrays.toString(nums));  
62.     }  
63. }