排序:(二)基本排序算法

基本排序算法:选择排序、插入排序、冒泡排序 这些排序算法适合小规模文件(例如,几十、上百个元素)和特殊结构文件。

排序算法的运行时间是和下列关系成正比:1.算法所执行的比较次数;2.元素移动或交换的次数。

1. 选择排序

选择排序的缺点是对文件中已有序的部分依赖少。 换句话说该算法没有充分利用文件中某些元素的有序信息。 这导致选择排序对元素随机排列的文件和有序排序的文件排序所花时间基本相同。

选择排序适合元素比较大,关键字比较小的文件,而其它算法的移动步数都比选择排序要多。

选择排序使用大约N^2/2次比较操作和N次交换操作。 选择排序时间中唯一对输入数据敏感的操作是寻找min的次数。 这个操作最坏情况下也是N^2次比较,平均为O(NlogN)。 因此可以说选择排序实行时间对输入数据不敏感。

2. 插入排序

和选择排序不同的是,插入排序的运行时间和输入文件的原始数据排列顺序密切相关。 如果文件较大,且关键字几乎是有序的,那么插入排序比选择排序要快。

更确切点说,对于逆序数是常数级的文件,插入排序和冒泡排序所要比较和交换的操作数目是输入的线性函数。

在平均情况下,插入排序执行大约N^2/4次比较和N^2/4次交换(移动)操作。 而在最坏情况下需要两倍的数量。

3. 冒泡排序

冒泡排序比较简单,比选择和插入排序要慢。

在平均情况和最坏情况下,冒泡排序执行大约N^2/2次比较操作和N^2/2次交换操作。

发表评论