发布时间 : 星期日 文章南邮数据结构上机实验四内排序算法的实现以及性能比较更新完毕开始阅读9883f069f9c75fbfc77da26925c52cc58ad69076
.
i=n-1; while(i>0) {
last=0;
for(j=0;j Swap(A[j],A[j+1]); last=j; } i=last; } } template void QuickSort(T A[],int n) //快速排序 { QSort(A,0,n-1); } template void QSort(T A[],int left,int right) { int i,j; if(left i=left; j=right+1; do { do i++;while (A[i] Swap(A[i],A[j]); }while(i Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } template void GQuickSort(T A[],int n) //改进的快速排序 { GQSort(A,0,n-1); } template . . void GQSort(T A[],int left,int right) { int i,j; if(right>=9) { if(left i=left; j=right+1; do { do i++;while (A[i] Swap(A[i],A[j]); }while(i Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } else { InsertSort(A,right-left+1); return ; } } template void Merge(T A[],int i1,int j1,int i2,int j2) //{ T* Temp=new T[j2-i1+1]; int i=i1,j=i2,k=0; while(i<=j1&&j<=j2) { if(A[i]<=A[j]) Temp[k++]=A[i++]; else Temp[k++]=A[j++]; } while (i<=j1) Temp[k++]=A[i++]; while(j<=j2) Temp[k++]=A[j++]; for(i=0;i . 两路合并排序 . delete[] Temp; } template void MergeSort(T A[],int n) { int i1,j1,i2,j2; int size=1; while(size i1=0; while(i1+size i2=i1+size; j1=i2-1; if(i2+size-1>n-1) j2=n-1; else j2=i2+size-1; Merge(A,i1,j1,i2,j2); i1=j2+1; } size*=2; } } int main() { clock_t start,finish; srand(time(NULL)); int n=1000; int *a=new int[n]; int *b=new int[n]; int *c=new int[n]; int *d=new int[n]; int *e=new int[n]; int *f=new int[n]; cout<<\待排序序列为:\ for(int i=0;i a[i]=rand()?; cout< . . e[i]=a[i]; f[i]=a[i]; } cout< start=clock(); SelectSort(a,n); cout<<\经过简单选择排序后的序列为:\ for(i=0;i cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); InsertSort(b,n); cout<<\经过直接插入排序后的序列为:\ for(i=0;i cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); BubbleSort(c,n); cout<<\经过冒泡排序后的序列为:\ for(i=0;i cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); QuickSort(d,n); cout<<\经过快速排序后的序列为:\ for(i=0;i cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); MergeSort(e,n); cout<<\经过两路合并排序后的序列为:\ for(i=0;i . 持续持续持续持续. cout< cout<<\开始时间为:\\结束时间为:\持续时间为:\ start=clock(); GQuickSort(f,n); cout<<\经过改进后的快速排序后的序列为:\ for(i=0;i cout<<\开始时间为:\\结束时间为:\时间为:\ return 0; } . 持续