内容发布更新时间 : 2024/11/16 16:41:30星期一 下面是文章的全部内容请认真阅读。
. . .
}
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）运行情况 主菜单 .......... . . . 直接插入排序 折半插入排序 ..........