源程序给出了插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序等多种排序算法，其...

// sorting.cpp : Defines the entry point for the console application. //#include "stdafx.h" #include "iostream.h" #include "stdlib.h" #include "time.h" #include "minheap.h" #include "LinQueue.h" #include "conio.h" // 使用getch() #include "stdlib.h" typedef int Keytype; const int Max=10; struct Datatype { Keytype key; Datatype(){} Datatype(Keytype item){key=item;} int operator <=(const Datatype &item) { return key<=item.key; } int operator <(const Datatype &item) { return key<item.key; } int operator ==(const Datatype &item) { return key==item.key; } int operator >=(const Datatype &item) { return key>=item.key; } int operator >(const Datatype &item) { return key>item.key; } int operator !=(const Datatype &item) { return key!=item.key; } }; //数组输出 void PrintOut(Datatype a[],int n) { cout<<"数组内容是："; for(int i=0;i<n;i++) cout<<a[i].key<<" "; cout<<endl; } //插入排序 void InsertSort(Datatype a[],int n) { int i,j; Datatype temp; for(i=0;i<n-1;i++) { temp=a[i+1]; /* 填空1 */ j=i; while(j>-1&&temp.key<a[j].key) { a[j+1]=a[j]; j--; } /* 填空2 */ a[j+1]=temp; } cout<<"完成了插入排序……"<<endl; } void SelectSort(Datatype a[],int n) { int i,j,small; Datatype temp; for(i=0;i<n-1;i++) { small=i; for(j=i+1;j<n;j++) if(a[j].key<a[small].key) small=j; if(small!=i) { /* 填空3 */ temp = a[i]; a[i] = a[small]; a[small] = temp; } } cout<<"完成了选择排序……"<<endl; } //希尔排序 void ShellSort(Datatype a[],int n) { int numOfD=3; int d[3]={6,3,1}; int i,j,k,m,span; Datatype temp; for(m=0;m<numOfD;m++) { span=d[m]; for(k=0;k<span;k++) { for(i=k;i<n-span;i = i+span/* 填空4 */) { temp=a[i+span]; j=i; while(j>-1&&temp.key<=a[j].key) { a[j+span]=a[j]; j=j-span; } /* 填空5 */ a[j+span] = temp; } } //中间输出 //PrintOut(a,n); } cout<<"完成了希尔排序……"<<endl; } //堆排序 void HeapSort(Datatype a[],int n) { MinHeap<Datatype> h1(a,n); //建立最大堆 Datatype temp; for(int i=n-1;i>0;i--) { //中间输出 //h1.PrintHeap(); temp=h1.Delete(); a[i]=temp; } cout<<"完成了堆排序……"<<endl; } //冒泡排序 void BubbleSort(Datatype a[],int n) { int i,j,flag=1; Datatype temp; for(i=1;i<n&&flag==1;i++) { flag=0; for(j=0;j<n-i;j++) if(a[j].key>a[j+1].key) { /* 填空6 */ flag = 1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } cout<<"完成了冒泡排序……"<<endl; } //双向冒泡 void DoubleBubbleSort(Datatype a[],int n) { int i,j,flag=1; Datatype temp; i=0; while (i<n && flag==1)/* 填空7 */ { flag=0; for(j=n-i-1;j>i;j--) if(a[j].key<a[j-1].key) { flag=1; temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } for(j=0; j<n-i-1; j++/* 填空8 */) if(a[j].key>a[j+1].key) { flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } i++; //中间输出 //PrintOut(a,n); } cout<<"完成了双向冒泡排序……"<<endl; } //快速排序 void QuickSort(Datatype a[],int low,int high) { int i=low,j=high; Datatype temp=a[low]; if (i==j) return; while(i<j) { while(/* 填空9 */i < j && temp.key <= a[j].key)j--; if(i<j) a[i++]=a[j]; while(i<j&&a[i].key<=temp.key)i++; if(i<j) a[j--]=a[i]; } a[i]=temp; // 输出中间结果 //cout<<"本次分区范围是："<<low<<" 至 "<<high<<" 基准元素是 "<<temp.key<<"位于 "<<i<<" 位置"<<endl; //for(int k=low;k<=high;k++) // cout<<a[k].key<<" "; //cout<<endl; if(low<i)QuickSort(/* 填空10 */ a,low,i-1); if(i<high)QuickSort(/* 填空11 */ a,j+1,high); } void QuickSort(Datatype a[],int n) { QuickSort(a,0,n-1); cout<<"完成了快速排序……"<<endl; } //归并排序 /*设每个有序表的长度为k，对表a[0]-a[n-1]中相邻的有序表进行两两归并， 结果存于swap[0]-swap[n-1]中，成为长度为2k的若干个有序表*/ void Merge(Datatype a[],int n,Datatype swap[],int k) { int m=0,u1,u2,l1=0,l2,i,j; while(l1+k<=n-1) { //当前的有序表1的下界是l1，上界是u1，有序表2的下界是l2，上界是u2 l2=l1+k; u1=l2-1; u2=(l2+k-1<=n-1)?l2+k-1:n-1; //表2的上界不能超界 // i是表1的指针，j是表2的指针 for(i=l1,j=l2;i<=u1&&j<=u2;m++) if(a[i].key<=a[j].key) swap[m]=a[i++]; else swap[m]=a[j++]; while(i<=u1) swap[m++]=a[i++]; //表2已结束，表1有余 while(j<=u2) swap[m++]=a[j++]; //表1已结束，表2有余 l1=u2+1; //往下处理后面的、长度为k的两个有序表 } for(i=l1;i<n;i++,m++)swap[m]=a[i];//剩余一表，无法与其他表归并，直接抄入 //输出中间结果： // cout<<endl<<"k="<<k<<" "; //for(i=0;i<n;i++)cout<<swap[i].key<<" "; } //归并排序 void MergeSort(Datatype a[],int n) { int i,k=1; Datatype *swap=new Datatype[n]; while(k<n) { Merge(a,n,swap,k); for(i=0;i<n;i++) a[i]=swap[i]; k=2*k; } delete []swap; cout<<"完成了归并排序……"<<endl; } //基数排序 void RadixSort(Datatype a[], int n, int m, int d) { int i,j,k,power=1; LinQueue<Datatype> *tub=new LinQueue<Datatype>[d]; for(i=0;i<m;i++) { if(i==0)power=1; else power=power *d/* 填空17 */; for(j=0;j<n;j++) { k=a[j].key/power-(a[j].key/(power*d))*d; tub[k].QInsert(a[j]); } for(j=0,k=0;j<d;j++) while(!tub[j].QueueEmpty()) { a[k++]=tub[j].QDelete(); //输出中间结果 //cout<<" "<<a[k-1].key; } //cout<<endl; } } //基数排序 void RadixSort(Datatype a[],int n) { RadixSort(a,n,3,10); cout<<"完成了基数排序……"<<endl; } //以下是递归的归并算法： void myMerge(Datatype olddata[],Datatype newdata[],int p,int m,int n) // olddata[p]..olddata[m] and olddata[m+1]..olddata[n]已排序, // 把这两个子表合并到 newdata[p]..newdata[n] { int i,j,k,a; //输出中间结果 //cout<<endl<<"olddata:"; //for(int q=p;q<=n;q++) cout<<" "<<olddata[q].key; i=p; j=m+1; k=p; while ((i<=m)&&(j<=n)) if (olddata[i]<=olddata[j]) newdata[k++]=olddata[i++]; else newdata[k++]=olddata[j++]; if (i<m+1) for (a=i;a<=m;a++) /* 填空12 */newdata[k++]=olddata[i++]; if (j<n+1) for (a=j;a<=n;a++)/* 填空13 */ newdata[k++]=olddata[j++]; //输出中间结果 //cout<<endl<<"newdata:"; //for( q=p;q<=n;q++) cout<<" "<<newdata[q].key; } void myMergesort(Datatype olddata[],Datatype newdata[],int s,int t) // 对olddata[s]..olddata[t]进行排序，结果仍存于olddata[s]..olddata[t] { int mid=(s+t)/2; if (s<=t) if (s==t) newdata[s]=olddata[s]; else { myMergesort(olddata,newdata,s,mid); /* 填空14 */ myMergesort(olddata,newdata,mid+1,t); /* 填空15 */ myMerge(olddata,newdata,s,mid,t); } /* 填空16 */ for(;s<=t;s++) olddata[s]=newdata[s]; } void myMergeSortALL(Datatype a[],int n) { Datatype *swap=new Datatype[n]; myMergesort(a,swap,0,n-1); delete []swap; cout<<"完成了递归的归并排序……"<<endl; } void main(void) { time_t t; Datatype test[Max]; srand((unsigned)time(&t)); int i; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); InsertSort(test,Max); PrintOut(test,Max); cout<<endl<<"开始新的排序："<<endl; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); SelectSort(test,Max); PrintOut(test,Max); cout<<" 看完后按任意键继续: "; cout<<endl; getch(); cout<<endl<<"开始新的排序："<<endl; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); ShellSort(test,Max); PrintOut(test,Max); cout<<endl<<"开始新的排序："<<endl; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); HeapSort(test,Max); PrintOut(test,Max); cout<<" 看完后按任意键继续: "; cout<<endl; getch(); cout<<endl<<"开始新的排序："<<endl; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); BubbleSort(test,Max); PrintOut(test,Max); cout<<endl<<"开始新的排序："<<endl; for (i=0;i<Max;i++) test[i]=rand()%100; PrintOut(test,Max); DoubleBubbleSort(test,Max