算法分析 设待排序对象个数为n,则该算法的主程序 执行n-1趟。 排序码比较次数和对象移动次数与对象排 序码的初始排列有关。 最好情况下,排序前对象已按排序码从小 到大有序,每趟只需与前面有序对象序列 的最后一个对象比较次移动次对象,总 的排序码比较次数为n-1,对象移动次数为 2(n-1)
11 算法分析 ◼ 设待排序对象个数为 n, 则该算法的主程序 执行n-1趟。 ◼ 排序码比较次数和对象移动次数与对象排 序码的初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小 到大有序, 每趟只需与前面有序对象序列 的最后一个对象比较1次, 移动2次对象, 总 的排序 码比较次数为 n-1, 对象移动次数为 2(n-1)
最坏情况下,第i趟时第i个对象必须与前 面i个对象都做排序码比较,并且每做1次 比较就要做1次数据移动。则总排序码比较 次数KCN和对象移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 RMM ∑(i+2)=(n+4)n-1)/2≈n2/2 在平均情况下的排序码比较次数和对象移 动次数约为n214。因此,直接插入排序的 时间复杂度为o(n2) 直接插入排序是一种稳定的排序方法。 12
12 ◼ 最坏情况下, 第 i 趟时第 i 个对象必须与前 面 i 个对象都做排序码比较, 并且每做1次 比较就要做1次数据移动。则总排序码比较 次数KCN和对象移动次数RMN分别为 ◼ 在平均情况下的排序码比较次数和对象移 动次数约为 n 2 /4。因此，直接插入排序的 时间复杂度为 o(n 2 )。 ◼ 直接插入排序是一种稳定的排序方法。 − = − = = + = + − = = − 1 1 1 1 2 4 1 2 2 1 2 2 n i n i RMN i n n n KCN i n n n ( ) ( )( )/ / ( )/ / , 2 2
希尔排序( Shell sort 希尔排序方法又称为缩小增量排序。该方法 的基本思想是:设待排序对象序列有n个对 象,首先取一个整数gap<n作为间隔,将全 部对象分为gap个子序列,所有距离为gap 的对象放在同一个子序列中,在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap,例如取gap=「gap21,重复上述的子序 列划分和排序工作。直到最后取gap==1 将所有对象放在同一个序列中排序为止。 13
13 希尔排序 (Shell Sort) ◼ 希尔排序方法又称为缩小增量排序。该方法 的基本思想是 : 设待排序对象序列有 n 个对 象, 首先取一个整数 gap < n 作为间隔, 将全 部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序 列划分和排序工作。直到最后取gap == 1, 将所有对象放在同一个序列中排序为止
49 25416 08 0 2 Gap=3 同 日r
14 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
2525 49 21□16 03 0 2 5 I=2 Gap=2 25 目园u 49 15
15 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