冒泡排序的算法分析 最好情况：初始排列已经有序，只执行一趟起泡，做-1 次关键码比较，不移动对象。 最坏情形：初始排列逆序，算法要执行-1趟起泡，第趟 (I≤衣m)做了m-i次关键码比较，执行了-i次对象交换。 此时的比较总次数KCN和记录移动次数RMW为： KCN (n-0-2an-) 1 n-1 3 因此： 时间效率：0(n)一因为要考虑最坏情况 空间效率：0(1)一只在交换时用到一个缓冲单元 稳定性：稳定一25和25*在排序前后的次序未改变
11 冒泡排序的算法分析 •最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。 •最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟 (1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换。 此时的比较总次数KCN和记录移动次数RMN为： − = − = = − = − = − = − 1 1 1 1 1 2 3 3 1 2 1 n i n i RMN n i n n KCN n i n n ( ) ( ) ( ) ( ) 因此： 时间效率：O（n2 ) —因为要考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 —25和25*在排序前后的次序未改变
冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一 个元素的位置（挤出一个泡到表尾），还可以对前面的元 素作一些整理，所以比一般的排序要快。 有没有比冒泡排序更快的算法？ 有！ 快速排序法一全球公认！ 因为它每趟都能准确定位不止1个 元素！ 12
12 冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一 个元素的位置（挤出一个泡到表尾），还可以对前面的元 素作一些整理，所以比一般的排序要快。 有没有比冒泡排序更快的算法？ 有！ 快速排序法——全球公认！ 因为它每趟都能准确定位不止1个 元素！
2)快速排序 基本思想： 从待排序列中任取一个元素（例如取第一个）作为中心， 所有比它小的元素一律前放，所有比它大的元素一律后放， 形成左右两个子表： 然后再对各子表重新选择中心元素并依此规则调整，直 到每个子表的元素只剩一个。此时便为有序序列了。 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增 加，所以特别快！ 前提：顺序存储结构 13
13 2） 快速排序 从待排序列中任取一个元素 (例如取第一个) 作为中心， 所有比它小的元素一律前放，所有比它大的元素一律后放， 形成左右两个子表； 然后再对各子表重新选择中心元素并依此规则调整，直 到每个子表的元素只剩一个。此时便为有序序列了。 基本思想： 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增 加，所以特别快！ 前提：顺序存储结构