学步园

整理旧的博客 2008-10-23 12:38:28

排序的python实现可以看

http://blog.csdn.net/wklken/archive/2011/04/11/6315567.aspx

--------------------------------------------------------------------

最近交的作业，测试成功，可以输出排序具体过程

汗，自己先用java写的，然后才使C++

可能某些地方用C++可以更简便灵活～～～多指教～～～

总的定义：

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

具体实现：

#include "SortNum.h"<br /> #include "iostream.h"<br /> //////////////////////////////////////////////////////////////////////<br /> // Construction/Destruction<br /> //////////////////////////////////////////////////////////////////////</p> <p>SortNum::SortNum()<br /> {</p> <p>}</p> <p>SortNum::~SortNum()<br /> {</p> <p>}</p> <p>//交换两个元素<br /> void SortNum::exchange(int& b,int& c)<br /> {<br /> int tem;<br /> tem=b;<br /> b=c;<br /> c=tem;<br /> }<br /> //输出数组所有元素<br /> void SortNum::listout(int a[],int n)<br /> {<br /> for(int i=0;i<n;i++)<br /> cout <<a[i]<<" ";<br /> cout <<endl;<br /> }</p> <p>//选择排序<br /> void SortNum::selectSort(int a[],int n)<br /> {<br /> for(int i=0;i<n-1;i++)<br /> {<br /> int k=i;<br /> for(int j=i+1;j<n;j++)<br /> if(a[j]<a[k])<br /> k=j;<br /> exchange(a[i],a[k]);<br /> listout(a,n);</p> <p> }<br /> }<br /> //冒泡排序<br /> void SortNum::bublbleSort(int a[],int n)<br /> {<br /> for(int i=n;i>1;i--)<br /> for(int j=0;j<i-1;j++)<br /> {<br /> if(a[j]>a[j+1])<br /> {<br /> exchange(a[j],a[j+1]);<br /> listout(a,n);</p> <p> }<br /> }<br /> }<br /> //插入排序<br /> void SortNum::insertSort(int a[],int n)<br /> {<br /> for(int i=1;i<n;i++)//从第二个元素开始<br /> {<br /> int tem=a[i];<br /> int j;<br /> for(j=i-1;j>=0 && tem<a[j];j--)//判断比其小的，因为前面已经排好序列了，所以可以比，然后后退<br /> a[j+1]=a[j];<br /> a[j+1]=tem;//插入<br /> listout(a,n);</p> <p> }<br /> }<br /> //基数排序<br /> void SortNum::baseSort(int a[],int n)<br /> {<br /> int r=10;//基数为十<br /> int tem=1;</p> <p> int max=a[0];<br /> for(int i=0;i<n;i++)//找出最大的，以在while中确定结束的时机<br /> {<br /> if(a[i]>max)<br /> max=a[i];<br /> }<br /> while((max%r)/tem !=0)//若最大的运算完为0.则整个基数排序结束<br /> {<br /> for(int i=n;i>1;i--)<br /> for(int j=0;j<i-1;j++)<br /> {<br /> if((a[j]%r)/tem>(a[j+1]%r)/tem)<br /> {<br /> exchange(a[j],a[j+1]);</p> <p> }<br /> }<br /> listout(a,n);</p> <p> tem *=10;<br /> r *=10;</p> <p> }</p> <p>}<br /> //快速排序<br /> void SortNum::quickSort(int a[],int n,int left,int right)<br /> {<br /> int i,j;<br /> i=left;<br /> j=right;<br /> int middle=a[(left+right)/2];<br /> do<br /> {<br /> while(a[i]<middle && i<right)//在左右找出一对，然后交换<br /> i++; //问1：没成对怎么办？只有一个比中间小的，怎么弄？</p> <p> //知道的吼！！<br /> while(a[j]>middle && j>left)<br /> j--;<br /> if(i<=j)<br /> {<br /> exchange(a[i],a[j]);<br /> i++;<br /> j--;<br /> listout(a,n);//输出有些问题，递归调用中也输出？？？</p> <p> }<br /> }while(i<=j);</p> <p> if(left<j)//递归调用排序左右两边，级级深入<br /> quickSort(a,n,left,j);<br /> if(right>i)<br /> quickSort(a,n,i,right);<br /> }<br /> //归并排序<br /> //二路归并 问题～～无法输出详细过程<br /> void SortNum::Merge(int *SR, int *TR, int i, int m, int n){</p> <p> // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]</p> <p> int j = m+1;</p> <p> int k = i;</p> <p> for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中</p> <p> if (SR[i]<=SR[j]){</p> <p> TR[k] = SR[i++];</p> <p> }else{</p> <p> TR[k] = SR[j++];</p> <p> }</p> <p> }</p> <p> while (i<=m) TR[k++] = SR[i++]; // 将剩余的 SR[i..m] 复制到TR</p> <p> while (j<=n) TR[k++] = SR[j++]; // 将剩余的 SR[j..n] 复制到TR</p> <p>}//Merge</p> <p>void SortNum::Msort( int *SR, int *TR1, int s, int t ){</p> <p> // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]</p> <p> if (s==t){</p> <p> TR1[s] = SR[s];</p> <p> }else {</p> <p> int TR2[7];//注：若main中数组改这里一定要改～～～～<br /> int m = (s+t)/2; // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]</p> <p> Msort(SR,TR2,s,m); // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]</p> <p> Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]</p> <p> Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]<br /> Copy(SR,TR1,s,t);</p> <p> }// else</p> <p>} // Msort<br /> void SortNum::Copy( int *S, int *T, int s, int t )<br /> {<br /> for(int i=s;i<=t;i++)<br /> S[i]=T[i];<br /> listout(S,7);<br /> }</p> <p>void main()<br /> {<br /> int a[7]={81,129,655,543,987,26,794};//问题：数组中了length怎么解决<br /> SortNum so;<br /> cout <<"原始数据"<<endl;<br /> so.listout(a,7);<br /> //so.exchange(a[0],a[1]);//测试exchange方法<br /> //so.listout(a,7);<br /> cout <<"选择排序类型：1.选择，2.冒泡，3.插入，4.基数 5.快速 6.归并"<<endl;<br /> int n;<br /> cin >>n;<br /> int b[7];<br /> switch( n)<br /> {<br /> case 1:so.selectSort(a,7);break;<br /> case 2:so.bublbleSort(a,7);break;<br /> case 3:so.insertSort(a,7);break;<br /> case 4:so.baseSort(a,7);break;<br /> case 5:so.quickSort(a,7,0,6);break;<br /> case 6:so.Msort(a,b,0,6);break;</p> <p> }</p> <p>}</p> <p>