排序算法
Acmer
9
7
<
7
<'。
冒泡排序最好的时间复杂度为 。
()算法的最坏时间复杂度
若初始文件是反序的,需要进行 趟排序。每趟排序要进行 次关键字的比较,且每
次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
9
7!A
<(<
7!A
<(<
冒泡排序的最坏时间复杂度为
。
()算法的平均时间复杂度为
虽然冒泡排序不一定要进行 趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排
序要差得多。
()算法稳定性
冒泡排序是就地排序,且它是稳定的。
5、算法改进
上述的冒泡排序还可做如下的改进:
记住最后一次交换发生位置 !,CA"/! 的冒泡排序
在每趟扫描中,记住最后一次交换发生的位置 !,CA"/!,(该位置之前的相邻记录均已有序)。
下一趟排序开始时,3!,CA"/!5是有序区,3!,CA"/!5是无序区。这样,一趟排序
可能使当前有序区扩充多个记录,从而减少排序的趟数。
改变扫描方向的冒泡排序
① 冒泡排序的不对称性
能一趟扫描完成排序的情况:
只有最轻的气泡位于 35的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。
【例】对初始关键字序列 ,?,,,,@,>,' 就仅需一趟扫描。
需要 趟扫描完成排序情况:
当只有最重的气泡位于 35的位置,其余的气泡均已排好序时,则仍需做 趟扫描才能完成排序。
【例】对初始关键字序列:>,',,?,,,,@ 就需七趟扫描。
② 造成不对称性的原因
每趟扫描仅能使最重气泡下沉一个位置,因此使位于顶端的最重气泡下沉到底部时,需做 趟扫
描。
③ 改进不对称性的方法
在排序过程中交替改变扫描方向,可改进不对称性
2.2 快速排序
1、算法思想
快速排序是 9BI! 于 > 年提出的一种划分交换排序。它采用了一种分治的策略,通常称
其为分治法JE%!%91#/%。
() 分治法的基本思想
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这
些子问题,然后将这些子问题的解组合为原问题的解。
()快速排序的基本思想
http://blog.csdn.net/qq_30368701