当n较大时,总排序码比较次数比直接插 入排序的最坏情况要好得多,但比其最好 情况要差。 在对象的初始排列已经按排序码排好序或 接近有序时,直接插入排序比折半插入排 序执行的排序码比较次数要少。折半插入 排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。 折半插入排序是一个稳定的排序方法。 16
16 ◼ 当 n 较大时, 总排序码比较次数比直接插 入排序的最坏情况要好得多, 但比其最好 情况要差。 ◼ 在对象的初始排列已经按排序码排好序或 接近有序时, 直接插入排序比折半插入排 序执行的排序码比较次数要少。折半插入 排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。 ◼ 折半插入排序是一个稳定的排序方法
希尔排序( Shell sort) 希尔排序方法又称为缩小增量排序。该方法 的基本思想是:设待排序对象序列有n个对 象,首先取一个整数gap<n作为间隔,将全 部对象分为gap个子序列,所有距离为gap 的对象放在同一个子序列中,在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap,例如取gap=「gap21,重复上述的子序 列划分和排序工作。直到最后取gap=1, 将所有对象放在同一个序列中排序为止
17 希尔排序 (Shell Sort) ◼ 希尔排序方法又称为缩小增量排序。该方法 的基本思想是 : 设待排序对象序列有 n 个对 象, 首先取一个整数 gap < n 作为间隔, 将全 部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序 列划分和排序工作。直到最后取gap == 1, 将所有对象放在同一个序列中排序为止
49 25416 08 0 2 Gap=3 同 日 18
18 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 08 49 Gap = 3 25 16 49 25 16 08 49 25* 08 21 21 25 25* 16
21□16 2525 49 0 0 2 5 I=2 Gap=2 目园u 49 同月
19 21 25 49 16 25* 08 0 1 2 3 4 5 21 i = 2 08 49 Gap = 2 25 16 49 16 25* 08 21 25 49 25* 08 16 21 25* 25
49 08 162125425 0 2 5 I=3 Gap=1 49 16 开始时gap的值较大,子序列中的对象较少, 排序速度较快;随着排序进展,gap值逐渐 变小,子序列中对象个数逐渐变多,由于前 面工作的基础,大多数对象已基本有序,所 以排序速度仍然很快。 20
20 21 25 49 16 25* 08 0 1 2 3 4 5 21 i = 3 08 Gap = 1 16 25 49 25* ◼ 开始时 gap 的值较大, 子序列中的对象较少, 排序速度较快; 随着排序进展, gap 值逐渐 变小, 子序列中对象个数逐渐变多, 由于前 面工作的基础, 大多数对象已基本有序, 所 以排序速度仍然很快