归并排序

冬冬

1. //下面两个函数全都是基于递归的的排序方法，效率都是相当不错的
   
2. #include <iostream>
   
3. #include <cstdlib>
   
4. #include <ctime>
   
5. using namespace std;
   
6. void MergeSort(int *array ,int first ,int last);//array为要排序的数组，first为要排序的开始位置，last为终止位置
   
7. void Merge(int *array,int p,int q,int r);//进行归并的函数
   
8. void Print(int *array,int begin,int end);  
   
9. void QuickSort(int *array,int fist,int last);  快排函数
   
10. int main()
    
11. {
    
12. int a[10];
    
13. int t;
    
14. srand(time(NULL));
    
15. 
    
16. for (int i=0;i<10;i++)
    
17. {
    
18.   t=rand()%100;
    
19.   a[i]=t;
    
20. }
    
21. cout<<"排序前——"<<endl;
    
22. Print(a,0,9);
    
23. // MergeSort(a,0,9);//归并
    
24. QuickSort(a,0,9);
    
25. cout<<"排序后——"<<endl;
    
26. Print(a,0,9);
    
27. return 0;
    
28. }
    
29. 
    
30. void Merge(int *array,int p,int q,int r)
    
31. {
    
32. int i,k;
    
33. int begin1,end1,begin2,end2;
    
34. int *temp = (int *)malloc((r-p+1)*sizeof(int));
    
35. begin1=p;
    
36. end1=q;
    
37. begin2=q+1;
    
38. end2=r;
    
39. k=0;
    
40. while((begin1<=end1)&&(begin2<=end2))
    
41. {
    
42.   if (array[begin1]<array[begin2])
    
43.   {
    
44.    temp[k]=array[begin1];
    
45.    begin1++;
    
46.   }
    
47.   else
    
48.   {
    
49.    temp[k]=array[begin2];
    
50.    begin2++;
    
51.   }
    
52.   k++;
    
53. }
    
54. while (begin1<=end1)
    
55. {
    
56.   temp[k++]=array[begin1++];
    
57. }
    
58. while (begin2<=end2)
    
59. {
    
60.   temp[k++]=array[begin2++];
    
61. }
    
62. for (i=0;i<=(r-p);i++)
    
63. {
    
64.   array[p+i]=temp[i];
    
65. }
    
66. free(temp);
    
67. 
    
68. }
    
69. void MergeSort(int *array ,int first ,int last)
    
70. {
    
71. int mid = 0;
    
72. if (first <last)
    
73. {
    
74.   mid = (first+last)/2;
    
75.   MergeSort(array,first,mid);
    
76.   MergeSort(array,mid+1,last);
    
77.   Merge(array,first , mid ,last );
    
78. }
    
79. }
    
80. 
    
81. void Print(int *array,int begin,int end)//begin，end为数组索引位置
    
82. {
    
83. for (int i=begin;i<=end;i++)
    
84. {
    
85.   cout<<array[i]<<"  ";
    
86. }
    
87. cout<<endl;
    
88. }
    
89. void QuickSort(int *array,int first,int last)
    
90. {
    
91. int base=array[first];
    
92. int x=first,y=last;
    
93. if (x>=y)
    
94. {
    
95.   return;
    
96. }
    
97. while(x<y)
    
98. {
    
99.   while(x<y && array[y]>=base)
    
100.   y--;
     
101.   array[x]=array[y];
     
102.   while(x<y && array[x]<=base)
     
103.   x++;
     
104.   array[y]=array[x];
     
105. }
     
106. 
     
107. array[y]=base;
     
108. QuickSort(array,first,x);
     
109. QuickSort(array,x+1,last);
     
110. }
     

复制代码

Be_envious

有点注释,或者能说一下算法的核心思想就好了
一上来就上一段代码
不是那么好理解

Cocol

看看学习学习

星晴☆之乐

有二路归并和三路归并一起的那种吗？他们在算法有什么不一样？还有怎么编比较次数和移动次数？

星晴☆之乐

三路归并怎么写啊？

sheri528