内容发布更新时间 : 2024/11/16 13:54:22星期一 下面是文章的全部内容请认真阅读。

. . .

}

break; case '2': cout<<\ *******您选择的是折半插入排序*******\\n\<

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?112(n?i)?(n?n)

2i?1 n32f) 移动次数： 3(n?i)?(n?n)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）运行情况

主菜单

..........

. . .

直接插入排序

折半插入排序

..........