PPT《东南大学计算机学院 方效林》

16 08

21 25

49 25*

16 08 gap= ?n/3?+1 =

3 21

16 08 25*

25 49 结果

21 16

08 25*

25 49 gap= ?gap/3?+1 =

2 21

16 08 25*

25 49

08 16

21 25*

25 49 结果

08 16

21 25*

25 49

08 16

21 25*

25 49 gap= ?gap/3?+1 =

1 结果 第2步第3步 最后1步是n个元素进行插入排序是不是很慢? 希尔排序 算法分析设定不同gap值,距离gap的元素放一起插入排序gap值越来越小,由于前面的排序过程,使得大多数数据已经基本有序,因此希尔排序速度仍然很快gap的取值方法有很多种gap= ?gap/3?+1gap= ?gap/2?……希尔排序复杂度分析很困难,还没有完整的数学分析统计得出,平均比较和移动次数在[n1.

25,1.6n1.25]内是不稳定的排序算法 * 快速排序 基本思想Partition:任取一元素x为基准(如选第1个),小于x的元素放在x左边,大于等于x的元素放在x右边对左、右部分递归执行上一步骤直至只有一个元素 *

21 25

49 25*

16 08 初始 第1层第2层第3层选21为基准 左部选08,右部选25*为基准 左部选16,右部选25为基准

08 16

21 25

49 25*

08 16

21 25*

25 49

08 16

21 25*

25 49 第4层 右部选49为基准

08 16

21 25*

25 49 快速排序 Partition(low,high)初始时基准坐标p = low, x=a[low]=21从i=low+1位置开始判断,比x小的元素与p下一个位置交换,p自加1循环直至i >

high,最后a[low]与a[p]交换 * p p p i p i>

high,停止 i a[low]与a[p]交换 a[i]与a[p+1]交换, p++ a[i]与a[p+1]交换, p++

21 25

49 25*

16 08

21 16

49 25*

25 08

21 16

08 25*

25 49

08 16

21 25*

25 49 * 作业:对数据a[N]进行快速排序的程序qsort(a[ ], 0, n-1) 快速排序 性能分析快速排序是一个递归算法 *

21 08

16 25*

25 49

08 16

21 25*

25 49 递归树 快速排序 性能分析快速排序的趟数取决于递归树的深度若每次选取的基准可将序列划分成长度相近的左、右两部分,则下一层将对两个长度减半的序列排序设原序列有n个元素,选基准和划分所需时间为O(n)设整个快速排序所需时间为T(n),则有:T(n) ≤ cn + 2T(n/2)c 是一个常数 ≤ cn + 2(cn/2 + 2T(n/4)) = 2cn + 4T(n/4)2cn + 4(cn/4 +2T(n/8)) = 3cn + 8T(n/8)cn log2n + nT(1) = O(nlog2n ) *

21 08

16 25*

25 49 快速排序 性能分析快速排序平均计算时间为O(nlog2n)平均计算时间是所有内部排序方法中最好的递归算法每层需保存递归调用的指针和参数平均情况下最大递归层数为?log2(n+1)?存储开销为O(log2n) * 快速排序 性能分析最坏情况单枝树,每次划分只得到比上一次少一个元素的序列比较次数递归树有n层,存储开销为O(n)快速排序是不稳定的算法 *

21 08

16 25*

25 49 快速排序 改进算法快速排序对长度很小的序列排序并不比直接插入快长度取5~25时,直接插入法比快速排序法快10%改进方法1:在快速排序递归过程中,当序列长度小于一定值时,使用直接插入排序法改进方法2:在快速排序递归过程中,当序列长度小于一定值时,退出排序得到一个整体上几乎已经排好序的序列对这个几乎已经排好序的序列使用直接插入排序法 * 快速排序 改进算法基准元素的选取对算法性能有很大影响改进方法1:可随机选择一个元素作为基准,避免最坏情况发生改进方法2:取左端点、右端点、中点(mid=?(left+right)/2?)这三个元素中的中间值作为基准 *

21 25

49 25*