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

.

5)6).

快速排序及其所需时间

改进快速排序及其所需时间

.

7) 两路合并排序及其所需时间

2. 结果分析

简单选择排序的最好、最坏的平均情况的时间复杂度都为O(n),是不稳定的排序方法；直接插入排序的最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n)；冒泡排序最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n)，是稳定的排序方法；快速排序最好情况的时间复杂度为O(n)，最坏情况的时间复

.

2

2

2

2

.

杂度为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;i

small=i;

for(int j=i+1;j

template

void InsertSort(T A[],int n) //直接插入排序 {

for(int i=1;i

int j=i; T temp=A[j];

while(j>0&&temp

A[j]=A[j-1]; j--; }

A[j]=temp; } }

template

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

int i,j,last;

.