希尔排序基本思想设定不同gap值，距离gap的元素放一起插入排序25*初始25*第1步gap=Ln/3J+1=325*25*25*结果25*gap=Lgap/3J+1=2第2步25*25*结果25*gap=Lgap/3J+1=1第3步最后1步是n个元素进行插入排序25*结果11是不是很慢？
希尔排序 ◼ 基本思想 设定不同gap值，距离gap的元素放一起插入排序 11 初始 25* 第1步 25* 25* 25* gap= n/3+1 = 3 结果 25* 25* gap= gap/3+1 = 2 25* 结果 25* 25* 25* gap= gap/3+1 = 1 结果 第2步 第3步 最后1步是n个元素进行插入排序 是不是很慢？
希尔排序算法分析口设定不同gap值，距离gap的元素放一起插入排序使得大多数gap值越来越小，由于前面的排序过程，数据已经基本有序，因此希尔排序速度仍然很快gap的取值方法有很多种gap=Lgap/3J+1gap=Lgap/2]希尔排序复杂度分析很困难，还没有完整的数学分析统计得出，平均比较和移动次数在[n1.25,1.6n1.25]内是不稳定的排序算法12
希尔排序 ◼ 算法分析 设定不同gap值，距离gap的元素放一起插入排序 ➢ gap值越来越小，由于前面的排序过程，使得大多数 数据已经基本有序，因此希尔排序速度仍然很快 ➢ gap的取值方法有很多种 gap= gap/3+1 gap= gap/2 . ➢ 希尔排序复杂度分析很困难，还没有完整的数学分析 ➢ 统计得出，平均比较和移动次数在[n1.25,1.6n1.25]内 ➢ 是不稳定的排序算法 12
快速排序基本思想口Partition：任取一元素x为基准（如选第1个)，小于+x的元素放在x左边，大于等于x的元素放在x右边对左、右部分递归执行上一步骤直至只有一个元素口初始25*25*第1层选21为基准25*第2层左部选08，右部选25*为基准25*第3层左部选16，右部选25为基准25*第4层右部选49为基准13
快速排序 ◼ 基本思想 Partition：任取一元素x为基准(如选第1个)，小于 x的元素放在x左边，大于等于x的元素放在x右边 对左、右部分递归执行上一步骤直至只有一个元素 13 初始 25* 第1层 第2层 第3层 选21为基准 左部选08，右部选25*为基准 左部选16，右部选25为基准 25* 25* 25* 第4层 25* 右部选49为基准