大家一起来排序吧
放假在家的时候,就想总结一下的,大二上学期学了数据结构,现在大二快结束了,估计不总结下就又要还给老师了。
就我了解的排序算法,除了归并排序之外,基本写了写,如有错误之处,还希望各位指正。
同样,排序是一门学问,说起它的用途,算法,太多了,我的视野比较窄,还希望各位前辈能给予补充排序算法。
比如说 补充归并排序,都用手写一写,敲一敲吧。
我把它稍微加工(封装不敢,自己C++比较烂)了下,弄成了一个类,同时用了下模板。
代码文件:Sorting.h--------------类声明文件
Sorting.cpp-------------------类实现文件
Test.cpp-------------------类测试文件
下面上代码:
C/C++ code
C/C++ code
C/C++ code
下面是程序运行截图:
最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):
大家回复盖楼补排序算法吧!让本贴的排序算法最多!COME ON!!!!!!
就我了解的排序算法,除了归并排序之外,基本写了写,如有错误之处,还希望各位指正。
同样,排序是一门学问,说起它的用途,算法,太多了,我的视野比较窄,还希望各位前辈能给予补充排序算法。
比如说 补充归并排序,都用手写一写,敲一敲吧。
我把它稍微加工(封装不敢,自己C++比较烂)了下,弄成了一个类,同时用了下模板。
代码文件:Sorting.h--------------类声明文件
Sorting.cpp-------------------类实现文件
Test.cpp-------------------类测试文件
下面上代码:
C/C++ code
//Sorting.h const int MaxSize=100; template<class T> class Sorting { public: Sorting(T a[],int n); void InsertDirectly(); void MiddleSearchSort(); int MiddleSearch(T data[],int low,int high,T value);//折半查找排序的折半查找函数 void ShellSort(); void ExchangeSort(); void QuickSort(int first,int end); int Partition(T *pdata,int first,int end);//快排的一次划分算法 void SelectSort(); void HeapSort(); void Sift(T a[],int k,int m);//调整堆算法 //数据成员,但由于需要在外部访问,故属性设置为public int length;//待排序的数的个数 T data[MaxSize];//待排序的数组 };
C/C++ code
//Sorting.cpp #include "Sorting.h" #include <iostream.h> template <class T> Sorting<T>::Sorting(T a[],int n) { length=n; for (int i=0;i<length;i++) { data[i]=a[i]; } } template<class T> void Sorting<T>::InsertDirectly() { //初始化一个b数组,其值从b[1]开始与a[0]相对.b[0]用来设置哨兵 T *b=new T[length+1]; for (int i=0;i<length;i++) { b[i+1]=data[i]; } b[0]=0; for (int j=2;j<length+1;j++) { b[0]=b[j]; for (int k=j-1;b[k]>b[0];k--) { b[k+1]=b[k]; } b[k+1]=b[0]; } //输出 for (int n=1;n<length+1;n++) { cout<<b[n]<<' '; } cout<<endl; } template<class T> void Sorting<T>::MiddleSearchSort() { //初始化一个b数组,其值从b[1]开始与a[0]相对.b[0]用来设置哨兵 T *b=new T[length+1]; for (int i=0;i<length;i++) { b[i+1]=data[i]; } b[0]=0; //使用折半查找来代替直接插入中的逐个移动 int low; for (int j=2;j<length+1;j++) { b[0]=b[j]; low=MiddleSearch(b,1,j-1,b[j]); for (int k=j-1;k>=low;k--) { b[k+1]=b[k]; } b[low]=b[0]; } //输出 for (int n=1;n<length+1;n++) { cout<<b[n]<<' '; } cout<<endl; } template<class T> int Sorting<T>::MiddleSearch(T data[],int low,int high,T value) { int mid; while(high>=low) { mid=(low+high)/2; if (value>data[mid]) { low=mid+1; } else if(value<data[mid]) { high=mid-1; } else { low=mid; break; } } return low; } template<class T> void Sorting<T>::ExchangeSort() { T *p=new T[length]; for (int l=0;l<length;l++) { p[l]=data[l]; } int exchange=length-1;//用来记录最后交换的位置 T middleValue;//用于交换值的时候作为中间值 int bound;//暂存exchange的值 while(exchange) { bound=exchange; exchange=0;//初始化exchange,如果没有交换则退出循环 for (int i=0;i<bound;i++) { //判断前一个和后一个的大小,如果后一个大的话,则交换. if(p[i]>p[i+1]) { middleValue=p[i]; p[i]=p[i+1]; p[i+1]=middleValue; //记录每次交换的位置 exchange=i; } } } for (int j=0;j<length;j++) { cout<<p[j]<<' '; } cout<<endl; } template<class T> void Sorting<T>::QuickSort(int first,int end) { int boundary; if (first<end) { boundary=Partition(data,first,end); QuickSort(first,boundary-1); QuickSort(boundary+1,end); } } template<class T> int Sorting<T>::Partition(T *pdata,int first,int end) { T exchangedata;//用于交换时作为中间值 while(first<end) { while(pdata[first]<=pdata[end] && first<end) end--; if (first<end) { exchangedata=pdata[first]; pdata[first]=pdata[end]; pdata[end]=exchangedata; first++; } while(pdata[first]<pdata[end] && first<end) first++; if (first<end) { exchangedata=pdata[first]; pdata[first]=pdata[end]; pdata[end]=exchangedata; end--; } } return first; } template<class T> void Sorting<T>::SelectSort() { T *p=new T[length]; for (int i=0;i<length;i++) { p[i]=data[i]; } int index;//记录所选择的值 T data;//用于交换数值时作为中间值 //一共进行length-1次选择比较 for (int k=0;k<length-1;k++) { index=k; for (int j=index;j<length-1;j++) { if (p[index]>p[j+1]) { index=j+1; } } //如果不相同则交换 if (index!=k) { data=p[index]; p[index]=p[k]; p[k]=data; } } for (int l=0;l<length;l++) { cout<<p[l]<<' '; } cout<<endl; } /* template<class T> void Sorting<T>::HeapSort() { T *p=new T[length]; for (int j=0;j<length;j++) { p[j]=data[j]; } T data;//用于交换时的中间值 //初始建堆,从最后一个非终端节点开始,直到根节点. for(int i=length/2-1;i>=0;i--) Sift(p,i,length-1); //重复执行移走堆顶以及重建堆的操作 for (int k=0;k<length-1;k++) { data=p[0]; p[0]=p[length-1-k]; p[length-1-k]=data; Sift(p,0,length-2-k); } for (int l=0;l<length;l++) { cout<<p[l]<<' '; } cout<<endl; } template<class T> void Sorting<T>::Sift(T a[],int k,int m) { //置i为要筛的节点,j为i的左孩子 int i,j; i=k;j=2*i; T data;//用于交换时的中间值 while(j<=m) { //比较i的左右孩子,j为较大者 if (j<m && a[j]<a[j+1]) { j++; } if (a[i]>a[j]) { //根节点已大于左右孩子中的较大者 break; } else { data=a[i]; a[i]=a[j]; a[j]=data; i=j;j=2*i;//将节点置于原来节点j的位置 } } } */ template<class T> void Sorting<T>::HeapSort() { T *p=new T[length+1]; for (int q=0;q<length;q++) { p[q+1]=data[q]; } p[0]=0; T data;//用于交换时的中间值 //初始建堆,从最后一个非终端节点开始,直到根节点. for(int i=length/2;i>=1;i--) Sift(p,i,length); //重复执行移走堆顶以及重建堆的操作 for (int k=1;k<length;k++) { data=p[1]; p[1]=p[length+1-k]; p[length+1-k]=data; Sift(p,1,length-k); } for (int l=1;l<=length;l++) { cout<<p[l]<<' '; } cout<<endl; } template<class T> void Sorting<T>::Sift(T a[],int k,int m) { //置i为要筛的节点,j为i的左孩子 int i,j; i=k;j=2*i; T data;//用于交换时的中间值 while(j<=m) { //比较i的左右孩子,j为较大者 if (j<m && a[j]<a[j+1]) { j++; } if (a[i]>a[j]) { //根节点已大于左右孩子中的较大者 break; } else { data=a[i]; a[i]=a[j]; a[j]=data; i=j;j=2*i;//将节点置于原来节点j的位置 } } } template<class T> void Sorting<T>::ShellSort() { T *p=new T[length+1]; for (int q=0;q<length;q++) { p[q+1]=data[q]; } p[0]=0; //以增量d进行直接插入排序 for (int d=length/2;d>=1;d=d/2) { for (int i=d+1;i<=length;i+=d)//待插入记录每次向后移动d个位置 { p[0]=p[i];//暂存被插入记录 for (int j=i-d;j>0 && p[0]<p[j];j=j-d) { p[j+d]=p[j];//记录后移d个位置 } p[j+d]=p[0]; } } for (int l=1;l<=length;l++) { cout<<p[l]<<' '; } cout<<endl; }
C/C++ code
//Test.cpp #include "Sorting.cpp" #include <iostream.h> int main() { double dbData[10]; cout<<"请输入10个double数(用空格分隔):"<<endl; for (int i=0;i<10;i++) { cin>>dbData[i]; } Sorting<double> st(dbData,10); cout<<"直接插入排序后:"<<endl; st.InsertDirectly(); cout<<"折半查找排序后:"<<endl; st.MiddleSearchSort(); cout<<"希尔排序之后:"<<endl; st.ShellSort(); cout<<"选择排序后:"<<endl; st.SelectSort(); cout<<"堆排序后:"<<endl; st.HeapSort(); cout<<"交换排序后:"<<endl; st.ExchangeSort(); cout<<"快速排序后:"<<endl; st.QuickSort(0,st.length-1); for (int j=0;j<st.length;j++) { cout<<st.data[j]<<' '; } cout<<endl; return 0; }
下面是程序运行截图:
最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):
大家回复盖楼补排序算法吧!让本贴的排序算法最多!COME ON!!!!!!
作者: xiaopo_poxiao 发布时间: 2011-06-12
郁闷 图小了。来个大的。
下面是程序运行截图:
最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):
上面这张不清楚的话 大家可以右键--图片另存为。保存到自己电脑上看。
好了。大家快点补充排序算法吧!谢谢各位前辈!!!!!!
下面是程序运行截图:
最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):
上面这张不清楚的话 大家可以右键--图片另存为。保存到自己电脑上看。
好了。大家快点补充排序算法吧!谢谢各位前辈!!!!!!
作者: xiaopo_poxiao 发布时间: 2011-06-12