- 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 );
- };
具体实现：
-
- #include "SortNum.h"
- #include "iostream.h"
- //////////////////////////////////////////////////////////////////////
- // Construction/Destruction
- //////////////////////////////////////////////////////////////////////
- SortNum::SortNum()
- {
- }
- SortNum::~SortNum()
- {
- }
- //交换两个元素
- void SortNum::exchange(int& b,int& c)
- {
- int tem;
- tem=b;
- b=c;
- c=tem;
- }
- //输出数组所有元素
- void SortNum::listout(int a[],int n)
- {
- for(int i=0;i<n;i++)
- cout <<a[i]<<" ";
- cout <<endl;
- }
- //选择排序
- void SortNum::selectSort(int a[],int n)
- {
- for(int i=0;i<n-1;i++)
- {
- int k=i;
- for(int j=i+1;j<n;j++)
- if(a[j]<a[k])
- k=j;
- exchange(a[i],a[k]);
- listout(a,n);
- }
- }
- //冒泡排序
- void SortNum::bublbleSort(int a[],int n)
- {
- for(int i=n;i>1;i--)
- for(int j=0;j<i-1;j++)
- {
- if(a[j]>a[j+1])
- {
- exchange(a[j],a[j+1]);
- listout(a,n);
- }
- }
- }
- //插入排序
- void SortNum::insertSort(int a[],int n)
- {
- for(int i=1;i<n;i++)//从第二个元素开始
- {
- int tem=a[i];
- int j;
- for(j=i-1;j>=0 && tem<a[j];j--)//判断比其小的，因为前面已经排好序列了，所以可以比，然后后退
- a[j+1]=a[j];
- a[j+1]=tem;//插入
- listout(a,n);
- }
- }
- //基数排序
- void SortNum::baseSort(int a[],int n)
- {
- int r=10;//基数为十
- int tem=1;
- int max=a[0];
- for(int i=0;i<n;i++)//找出最大的，以在while中确定结束的时机
- {
- if(a[i]>max)
- max=a[i];
- }
- while((max%r)/tem !=0)//若最大的运算完为0.则整个基数排序结束
- {
- for(int i=n;i>1;i--)
- for(int j=0;j<i-1;j++)
- {
- if((a[j]%r)/tem>(a[j+1]%r)/tem)
- {
- exchange(a[j],a[j+1]);
- }
- }
- listout(a,n);
- tem *=10;
- r *=10;
- }
- }
- //快速排序
- void SortNum::quickSort(int a[],int n,int left,int right)
- {
- int i,j;
- i=left;
- j=right;
- int middle=a[(left+right)/2];
- do
- {
- while(a[i]<middle && i<right)//在左右找出一对，然后交换
- i++; //问1：没成对怎么办？只有一个比中间小的，怎么弄？
- //知道的吼！！
- while(a[j]>middle && j>left)
- j--;
- if(i<=j)
- {
- exchange(a[i],a[j]);
- i++;
- j--;
- listout(a,n);//输出有些问题，递归调用中也输出？？？
- }
- }while(i<=j);
- if(left<j)//递归调用排序左右两边，级级深入
- quickSort(a,n,left,j);
- if(right>i)
- quickSort(a,n,i,right);
- }
- //归并排序
- //二路归并 问题～～无法输出详细过程
- void SortNum::Merge(int *SR, int *TR, int i, int m, int n){
- // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
- int j = m+1;
- int k = i;
- for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中
- if (SR[i]<=SR[j]){
- TR[k] = SR[i++];
- }else{
- TR[k] = SR[j++];
- }
- }
- while (i<=m) TR[k++] = SR[i++]; // 将剩余的 SR[i..m] 复制到TR
- while (j<=n) TR[k++] = SR[j++]; // 将剩余的 SR[j..n] 复制到TR
- }//Merge
- void SortNum::Msort( int *SR, int *TR1, int s, int t ){
- // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]
- if (s==t){
- TR1[s] = SR[s];
- }else {
- int TR2[7];//注：若main中数组改这里一定要改～～～～
- int m = (s+t)/2; // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]
- Msort(SR,TR2,s,m); // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]
- Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
- Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]
- Copy(SR,TR1,s,t);
- }// else
- } // Msort
- void SortNum::Copy( int *S, int *T, int s, int t )
- {
- for(int i=s;i<=t;i++)
- S[i]=T[i];
- listout(S,7);
- }
- void main()
- {
- int a[7]={81,129,655,543,987,26,794};//问题：数组中了length怎么解决
- SortNum so;
- cout <<"原始数据"<<endl;
- so.listout(a,7);
- //so.exchange(a[0],a[1]);//测试exchange方法
- //so.listout(a,7);
- cout <<"选择排序类型：1.选择，2.冒泡，3.插入，4.基数 5.快速 6.归并"<<endl;
- int n;
- cin >>n;
- int b[7];
- switch( n)
- {
- case 1:so.selectSort(a,7);break;
- case 2:so.bublbleSort(a,7);break;
- case 3:so.insertSort(a,7);break;
- case 4:so.baseSort(a,7);break;
- case 5:so.quickSort(a,7,0,6);break;
- case 6:so.Msort(a,b,0,6);break;
- }
- }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
