六种排序的C++实现-阿里云开发者社区

六种排序的C++实现

2013-08-10 619

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： class SortNum { public: SortNum(); virtual ~SortNum(); void exchange(int& b,int& c);//交换数据 void listout(int a[],int n);/...

class SortNum
{
public:
SortNum();
virtual ~SortNum();
void exchange(int& b,int& c);//交换数据
void listout(int a[],int n);//列出所有
void selectSort(int a[],int n);//选择
void bublbleSort(int a[],int n);//冒泡
void insertSort(int a[],int n);//插入
void baseSort(int a[],int n);//基数
void quickSort(int a[],int n,int left,int right);//快速
void Merge(int *SR, int *TR, int i, int m, int n);//归并
void Msort( int *SR, int *TR1, int s, int t );
void Copy( int *S, int *T, int s, int t );
};

具体实现：

view plain copy to clipboard print ?

1. #include "SortNum.h"
2. #include "iostream.h"
3. //////////////////////////////////////////////////////////////////////
4. // Construction/Destruction
5. //////////////////////////////////////////////////////////////////////
7. SortNum::SortNum()
8. {
11. }
13. SortNum::~SortNum()
14. {
16. }
18. //交换两个元素
19. void SortNum::exchange(int& b,int& c)
20. {
21. int tem;
22. tem=b;
23. b=c;
24. c=tem;
25. }
26. //输出数组所有元素
27. void SortNum::listout(int a[],int n)
28. {
29. for(int i=0;i<n;i++)
30. cout <<a[i]<<" ";
31. cout <<endl;
32. }
35. //选择排序
36. void SortNum::selectSort(int a[],int n)
37. {
38. for(int i=0;i<n-1;i++)
39. {
40. int k=i;
41. for(int j=i+1;j<n;j++)
42. if(a[j]<a[k])
43. k=j;
44. exchange(a[i],a[k]);
45. listout(a,n);
47. }
48. }
49. //冒泡排序
50. void SortNum::bublbleSort(int a[],int n)
51. {
52. for(int i=n;i>1;i--)
53. for(int j=0;j<i-1;j++)
54. {
55. if(a[j]>a[j+1])
56. {
57. exchange(a[j],a[j+1]);
58. listout(a,n);
60. }
61. }
62. }
63. //插入排序
64. void SortNum::insertSort(int a[],int n)
65. {
66. for(int i=1;i<n;i++)//从第二个元素开始
67. {
68. int tem=a[i];
69. int j;
70. for(j=i-1;j>=0 && tem<a[j];j--)//判断比其小的，因为前面已经排好序列了，所以可以比，然后后退
71. a[j+1]=a[j];
72. a[j+1]=tem;//插入
73. listout(a,n);
75. }
76. }
77. //基数排序
78. void SortNum::baseSort(int a[],int n)
79. {
80. int r=10;//基数为十
81. int tem=1;
84. int max=a[0];
85. for(int i=0;i<n;i++)//找出最大的，以在while中确定结束的时机
86. {
87. if(a[i]>max)
88. max=a[i];
89. }
90. while((max%r)/tem !=0)//若最大的运算完为0.则整个基数排序结束
91. {
92. for(int i=n;i>1;i--)
93. for(int j=0;j<i-1;j++)
94. {
95. if((a[j]%r)/tem>(a[j+1]%r)/tem)
96. {
97. exchange(a[j],a[j+1]);
99. }
100. }
101. listout(a,n);
103. tem *=10;
104. r *=10;
106. }
108. }
109. //快速排序
110. void SortNum::quickSort(int a[],int n,int left,int right)
111. {
112. int i,j;
113. i=left;
114. j=right;
115. int middle=a[(left+right)/2];
116. do
117. {
118. while(a[i]<middle && i<right)//在左右找出一对，然后交换
119. i++; //问1：没成对怎么办？只有一个比中间小的，怎么弄？
121. //知道的吼！！
122. while(a[j]>middle && j>left)
123. j--;
124. if(i<=j)
125. {
126. exchange(a[i],a[j]);
127. i++;
128. j--;
129. listout(a,n);//输出有些问题，递归调用中也输出？？？
131. }
132. }while(i<=j);
134. if(left<j)//递归调用排序左右两边，级级深入
135. quickSort(a,n,left,j);
136. if(right>i)
137. quickSort(a,n,i,right);
138. }
139. //归并排序
140. //二路归并问题～～无法输出详细过程
141. void SortNum::Merge(int *SR, int *TR, int i, int m, int n){
143. // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
145. int j = m+1;
147. int k = i;
149. for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中
151. if (SR[i]<=SR[j]){
153. TR[k] = SR[i++];
155. }else{
157. TR[k] = SR[j++];
159. }
161. }
163. while (i<=m) TR[k++] = SR[i++]; // 将剩余的 SR[i..m] 复制到TR
165. while (j<=n) TR[k++] = SR[j++]; // 将剩余的 SR[j..n] 复制到TR
167. }//Merge
169. void SortNum::Msort( int *SR, int *TR1, int s, int t ){
171. // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]
173. if (s==t){
175. TR1[s] = SR[s];
177. }else {
180. int TR2[7];//注：若main中数组改这里一定要改～～～～
181. int m = (s+t)/2; // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]
183. Msort(SR,TR2,s,m); // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]
185. Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
187. Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]
188. Copy(SR,TR1,s,t);
190. }// else
192. } // Msort
193. void SortNum::Copy( int *S, int *T, int s, int t )
194. {
195. for(int i=s;i<=t;i++)
196. S[i]=T[i];
197. listout(S,7);
198. }
203. void main()
204. {
205. int a[7]={81,129,655,543,987,26,794};//问题：数组中了length怎么解决
206. SortNum so;
207. cout <<"原始数据"<<endl;
208. so.listout(a,7);
209. //so.exchange(a[0],a[1]);//测试exchange方法
210. //so.listout(a,7);
211. cout <<"选择排序类型：1.选择，2.冒泡，3.插入，4.基数 5.快速 6.归并"<<endl;
212. int n;
213. cin >>n;
214. int b[7];
215. switch( n)
216. {
217. case 1:so.selectSort(a,7);break;
218. case 2:so.bublbleSort(a,7);break;
219. case 3:so.insertSort(a,7);break;
220. case 4:so.baseSort(a,7);break;
221. case 5:so.quickSort(a,7,0,6);break;
222. case 6:so.Msort(a,b,0,6);break;
224. }
226. }

微信公众号：猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。

六种排序的C++实现

热门文章

最新文章

相关课程

相关电子书