实验?/p>
内排序算法比?/p>
本实验目的是使读者,掌握常用排序方法的基本思想,通过实验加深理解各种排序算法,通过?/p>
验掌握各种排序方法的时间复杂度分析,了解各种排序方法的优缺点及适用范围?/p>
1
.排序算法的实现(设计性实验)
【问题描述?/p>
排序是计算机领域的一项重要技术,
是程序设计中的一种重要运算?/p>
它的功能是将一个数据元?/p>
的任意序列重新排列成一个按键有序的序列?/p>
【基本要求?/p>
1.
产生系统菜单,菜单项如下?/p>
[1]
退?/p>
[2]
产生随机?/p>
[3]
使用直接插入排序算法进行排序
[4]
使用折半插入排序算法进行排序
[5]
使用冒泡排序算法进行排序
[6]
使用简单选择排序算法进行排序
[7]
打印数组内容(或输出内容到文件)
2.
随机产生
n
个整数(大小范围?/p>
0~9999
?/p>
,将其存于数?/p>
A[0..n-1]
中?/p>
n
可由用户输入,测
试时?/p>
n
赋?/p>
100
?/p>
200
?/p>
300
?/p>
1 000
?/p>
2 000
及更多。调用相应的算法进行排序,然后输出?/p>
【选做要求?/p>
1.
在以上基础实现堆排序和快速排序算法?/p>
2.
对各个算法进行实验比较,计算出平均比较次?/p>
c
n
、平均移动次?/p>
m
n
?/p>
c
n
?/p>
m
n
由总比较次?
和总移动次数除以个?/p>
n
所得?/p>
3.
对实验结果数据进行对比分析?/p>
?/p>
n
可从
100,200,1000,2000,10000
?/p>
20000
……逐步增加?/p>
【测试数据?/p>
产生随机数的算法可参考如下:需包含以下两个头文?/p>
<iomanip>
?/p>
<time.h>