南邮数据结构上机实验四内排序算法的实现以及性能比较(3)

杂度为O(nlog2n)，是不稳定的排序方法；两路合并排序的时间复杂度为O(nlog2n)，是稳定的排序方法。

六、 实习小结

在这次实验中,我们对内部排序算法进行了比较以及性能分析,通过这次实验,我们加深了对内部排序算法的理解,对内部排序算法的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。

通过这次实验，我明白了，没有总是最好的排序方法。对于一般列表，快速排序、希的性能较好。通过本次实验，我深刻体会到问题解决方案的重要性，算法效率分析的必要性。法时。

附录：

#include #include #include template

void Swap(T &a,T &b) { T temp=a; a=b; b=temp; }

template

void SelectSort(T A[],int n) //简单选择排序 { int small; for(int i=0;itemplate

void InsertSort(T A[],int n) //直接插入排序 { for(int i=1;i0&&temp

template

void BubbleSort(T A[],int n) //冒泡排序 { int i,j,last;

i=n-1; while(i>0) { last=0; for(j=0;jtemplate

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

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

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(sizen-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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库南邮数据结构上机实验四内排序算法的实现以及性能比较(3)在线全文阅读。