内容发布更新时间 : 2024/12/23 6:50:05星期一 下面是文章的全部内容请认真阅读。
}
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)运行情况 主菜单 直接插入排序 折半插入排序 冒泡排序 简单选择排序