六种排序的C++实现

时间：2024-01-12 21:39:08
  1. class SortNum
  2. {
  3. public:
  4. SortNum();
  5. virtual ~SortNum();
  6. void exchange(int& b,int& c);//交换数据
  7. void listout(int a[],int n);//列出所有
  8. void selectSort(int a[],int n);//选择
  9. void bublbleSort(int a[],int n);//冒泡
  10. void insertSort(int a[],int n);//插入
  11. void baseSort(int a[],int n);//基数
  12. void quickSort(int a[],int n,int left,int right);//快速
  13. void Merge(int *SR, int *TR, int i, int m, int n);//归并
  14. void Msort( int *SR, int *TR1, int s, int t );
  15. void Copy( int *S, int *T, int s, int t );
  16. };

具体实现：

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

相关文章