求内部排序算法的比较
通过内部排序算法实现,帮助学生熟练掌握各种排序算法的基本技术。通过各种排序算法在数据随机分布、正序和逆序情况下,数据比较次数和数据元素移动次数,对不同排序算法的时间复杂读获得只管的感受。实现6中常用内部排序算法:
直接插入排序
希尔派序
冒泡排序
快速排序
简单选择排序
堆排序
对每种排序方法,记录其数据比较次数和数据移动次数。
要求待排序数据不少于100,数据分布在一个较大的范围内,若1000。
待排序序列考虑三种数据分布:
数据序列随机分布
数据序列递增有序
数据序列递减有序
1、随机序列生成
随机数可用C语言函数库提供的随机数生成函数random自动升,其格式为:
random(<整型常数>)
该函数随机产生不大于指定常数的正整数。若连续地产生随机数,有可能出现重复的随机数。如果不希望出现重复的数据,在产生的过程中英滤去重复的数据。
2、比较次数和元素移动次数计算
算法只考虑元素的参与的比较和移动。对于条件表达式,若无元素参与比较,则不对其进行比较计数。没有元素参与的赋值运算,则不对其进行移动计数。
(1)比较次数的计算:凡是由元素参与比较运算,比较计数器要加1。
(2)数据移动次数的计算:将一个元素的值赋给另一个元素,即表示数据的一次移动。如果有两个元素互相交换值,则表示有3次数据移动。