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

复制代码

附上测试结果
归并排序用时:42毫秒

麦子兄，赞！
能写上系统点的思路给俺这小白看就好了

神之梦 发表于 2013-6-13 08:26
麦子兄，赞！
能写上系统点的思路给俺这小白看就好了

考研期间复习数据结构总结的
喜欢的话  就给我技术分咯

麦子 发表于 2013-6-13 23:54
考研期间复习数据结构总结的
喜欢的话  就给我技术分咯

可惜我没有权限啊，你把觉得可以加分的帖去袁骑士有个加分帖下贴贴，会给加的

支持一个。。。。