数据结构课程设计报告---几种排序算法的演示(附源代码) 下载本文

}

break;

system(\); break; case '3':

cout<<\您选择的是冒泡排序*******\\n\<

system(\); break; case '4':

cout<<\您选择的是简单选择排序*******\\n\<

system(\); break; case '5':

cout<<\您选择的是快速排序*******\\n\<

system(\); break; case '6':

cout<<\您选择的是堆排序*******\\n\<

system(\); break; case '7':

cout<<\您选择的是归并排序*******\\n\<

system(\); break; } } }

system(\); return 0;

三 上机结果及体会

1) 实际完成的情况说明

此程序主要实现了对不同排序算法的演示,并给出了每一趟的变化情况

2) 程序的性能分析

a. 直接插入排序(稳定的排序方法)

1时间复杂度

a) 若待排序记录按关键字从小到大排列(正序)

n?1关键字比较次数:

1?n?1 i?1记录移动次数:2(n-1)

b)若待排序记录按关键字从大到小排列(逆序)

n 1关键字比较次数: n(n?1)n2i?? 22i?1

n 1记录移动次数: (n?4)(n?1)n2(i?2)?? 22i?1

c) 若待排序记录是随机的,取最好和最坏情况的平均值

n2关键字比较次数(约为):4

n2记录移动次数(约为):

4

2空间复杂度:S(n)=O(1)

b. 折半插入排序(稳定的排序算法)

就平均性能而言,因为折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。

关键字的比较次数为:n*log2(n) c. 冒泡排序(稳定的排序算法)

1. 时间复杂度:

a) 最好情况(正序)

b) 比较次数:n-1(只要进行一趟即可) c) 移动次数:0

d) 最坏情况(逆序)

e) 比较次数:(需n-1趟,每趟达到最大比较次数)

n?1 12(n?i)?(n?n)

2i?1 n323(n?i)?(n?n)f) 移动次数:

2i?1在最坏情况下,时间复杂度为:T(n)=O(n2) 2. 空间复杂度:S(n)=O(1)

d. 简单选择排序(不稳定的排序方法)

1. 时间复杂度:O(n2)。 2. 空间复杂度:S(1)。

e. 快速排序(不稳定的排序方法)

1.时间复杂度

最好情况(每次总是选到中间值作枢轴)T(n)=O(nlog2n)

?????最坏情况(每次总是选到最小或最大元素作枢轴)T(n)=O(n2)

2.空间复杂度:需栈空间以实现递归

最坏情况:S(n)=O(n) 一般情况:S(n)=O(log2n)

f. 堆排序(不稳定的排序方法)] 1.间复杂性为O(nlog2n)。 2空间复杂性为O(1)。 g. 归并排序(稳定的排序方法)

1时间复杂度为O(nlog2n)。 2空间复杂度为O(n)。

3)运行情况

主菜单

直接插入排序

折半插入排序

冒泡排序

简单选择排序