六种排序的C++实现

2021-07-06 03:14:56

  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.    
  14.  void Merge(int *SR, int *TR, int i, int m, int n);//归并  
  15.  void Msort( int *SR, int *TR1, int s, int t );  
  16.  void Copy( int *S, int *T, int s, int t );  
  17.   
  18. };  

  

 

具体实现：

 

view plaincopy to clipboardprint?
    1. #include "SortNum.h"  
    2. #include "iostream.h"  
    3. //////////////////////////////////////////////////////////////////////  
    4. // Construction/Destruction  
    5. //////////////////////////////////////////////////////////////////////  
    6.   
    7. SortNum::SortNum()  
    8. {  
    9.    
    10.   
    11. }  
    12.   
    13. SortNum::~SortNum()  
    14. {  
    15.   
    16. }  
    17.   
    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. }  
    33.   
    34.   
    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);  
    46.      
    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);  
    59.        
    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);  
    74.     
    75.   }  
    76. }  
    77. //基数排序  
    78. void SortNum::baseSort(int a[],int n)  
    79. {  
    80.       int r=10;//基数为十  
    81.    int tem=1;  
    82.     
    83.     
    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]);  
    98.         
    99.      }  
    100.     }  
    101.    listout(a,n);  
    102.     
    103.    tem *=10;  
    104.    r *=10;  
    105.    
    106.   }  
    107.   
    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：没成对怎么办？只有一个比中间小的，怎么弄？  
    120.   
    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);//输出有些问题，递归调用中也输出？？？  
    130.       
    131.    }  
    132.   }while(i<=j);  
    133.      
    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){  
    142.   
    143.     // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]  
    144.   
    145.     int j = m+1;  
    146.   
    147.     int k = i;  
    148.   
    149.     for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中  
    150.   
    151.         if (SR[i]<=SR[j]){  
    152.   
    153.             TR[k] = SR[i++];  
    154.   
    155.         }else{  
    156.   
    157.             TR[k] = SR[j++];  
    158.   
    159.         }  
    160.   
    161.     }  
    162.   
    163.     while (i<=m) TR[k++] = SR[i++];   // 将剩余的 SR[i..m] 复制到TR  
    164.   
    165.     while (j<=n) TR[k++] = SR[j++];   // 将剩余的 SR[j..n] 复制到TR  
    166.   
    167. }//Merge  
    168.   
    169. void SortNum::Msort( int *SR, int *TR1, int s, int t ){  
    170.   
    171.     // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]  
    172.   
    173.     if (s==t){  
    174.   
    175.         TR1[s] = SR[s];  
    176.   
    177.     }else {  
    178.   
    179.          
    180.         int TR2[7];//注：若main中数组改这里一定要改～～～～  
    181.         int m = (s+t)/2;   // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]  
    182.   
    183.         Msort(SR,TR2,s,m);  // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]  
    184.   
    185.         Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]  
    186.   
    187.         Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]  
    188.       Copy(SR,TR1,s,t);  
    189.   
    190.     }// else  
    191.   
    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. }  
    199.   
    200.    
    201.   
    202.   
    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;  
    223.   
    224.  }  
    225.    
    226. }

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

上一篇：Upload-labs 文件上传靶场通关攻略(下)


下一篇：webpack(四)之babel