1. 
   
2. <P>import java.util.Date;
   
3. public class Sort {
   
4. 
   
5. /**
   
6. * 作者：麦子
   
7. * 功能：实现归并排序排序算法
   
8. */
   
9. public static void main(String[] args) {
   
10. int len=100000;
    
11. int[] arrg=new int[len];
    
12. for(int i=0;i<len;i++){
    
13. int t=(int)(Math.random()*100);
    
14. arrg[i]=t;
    
15. }
    
16. Merger sort7 = new Merger();
    
17. Date date12 = new Date();
    
18. long a12 = date12.getTime();
    
19. sort7.sort(arrg);
    
20. Date date13 = new Date();
    
21. long a13 = date13.getTime();
    
22. System.out.println("归并排序用时:"+(a13-a12)+"毫秒");
    
23. }
    
24. 
    
25. }
    
26. 
    
27. class Merger extends Sort{
    
28. int[][] tdarr;//由于还不知道数组长度,故先声明一个二维数组，用途为存放数组数据
    
29. //排序的方法
    
30. public void sort(int arr[])
    
31. {
    
32. int j;//j控制的是二维
    
33. tdarr = new int[arr.length][1];//方法的形参列表中引入了数组，即可实例化上面的声明的那个二维数组
    
34. for(j=0;j<arr.length;j++)
    
35. { tdarr[j][0] = arr[j]; }
    
36. --j;
    
37. while(tdarr[0].length<arr.length)
    
38. {
    
39. if(j%2==0){
    
40. j/=2;
    
41. int m;
    
42. for(m=0;m<j;m++)
    
43. { //将tdarr[m/2]指向归并后的数组的地址
    
44. tdarr[m] = merge(tdarr[2*m],tdarr[2*m+1],
    
45. tdarr[2*m].length,tdarr[2*m+1].length);
    
46. }
    
47. //将tdarr[m/2]指向归并后的数组的地址
    
48. tdarr[m] = tdarr[2*m];
    
49. }else{
    
50. j/=2;
    
51. j++;
    
52. for(int m=0;m<j;m++)
    
53. { //将tdarr[m/2]指向归并后的数组的地址
    
54. tdarr[m] = merge(tdarr[2*m],tdarr[2*m+1],
    
55. tdarr[2*m].length,tdarr[2*m+1].length);
    
56. }
    
57. j--;
    
58. }
    
59. }
    
60. }
    
61. //归并两个数组的方法，此方法逻辑较为复杂,请耐心品味
    
62. public int[] merge(int arr0[],int arr1[],int x,int y){
    
63. //int x、y分别表示数组arr0、arr1的长度,为什么不直接用arr0.length、arr1.length
    
64. //是为了增强代码的可读性,以免看得云里雾里
    
65. int low0 = 0,high0 = 0,low1 = 0,high1 = 0;
    
66. //low0、high0、low1、high1分别表示的是数组arr0、arr1各自的低位指针、高位指针
    
67. int[] _arr = new int[x+y];//数组_arr用来存放归并两个子数组后的总数组
    
68. while(high0<x||high1<y){
    
69. while(high0<x&&arr0[high0]<=arr1[low1])
    
70. { high0++; }
    
71. if(high1!=y&&high0==x)
    
72. {
    
73. for(int i=low0;i<high0;i++)
    
74. { _arr[low1+i] = arr0[i]; }
    
75. for(int i=low1;i<y;i++)
    
76. {
    
77. high1++;
    
78. _arr[high0+i] = arr1[i];
    
79. }
    
80. }//此处即已排完
    
81. else if(high0<x)
    
82. {
    
83. for(int i=low0;i<high0;i++)
    
84. { _arr[low1+i] = arr0[i]; }
    
85. low0 = high0;
    
86. }
    
87. while(high1<y&&arr0[low0]>=arr1[high1])
    
88. { high1++; }
    
89. if(high0!=x&&high1==y)
    
90. {
    
91. for(int i=low1;i<high1;i++)
    
92. { _arr[low0+i] = arr1[i]; }
    
93. for(int i=low0;i<x;i++)
    
94. {
    
95. high0++;
    
96. _arr[high1+i] = arr0[i];
    
97. }
    
98. }//此处即已排完
    
99. else if(high1<y)
    
100. {
     
101. for(int i=low1;i<high1;i++)
     
102. { _arr[low0+i] = arr1[i]; }
     
103. low1 = high1;
     
104. }
     
105. }
     
106. return _arr;//返回归并后的数组,为什么不采用返回类型void,然后后arr0=_arr.
     
107. } //请自行了解值传递与引用传递的区别
     
108. //打印的方法
     
109. public void show()
     
110. {
     
111. for(int i=0;i<tdarr[0].length;i++)
     
112. {
     
113. System.out.print(tdarr[0][i]+" ");
     
114. }
     
115. }
     
116. }</P>
     
117. <P> </P>
     
118. <P>/***附上测试结果</P>
     
119. <P>*归并排序用时:45毫秒</P>
     
120. <P>*/</P>

复制代码

学习了，感谢