算法设计与分析：插入排序

阅读量：

算法思想：

我们可以将序列 $A$ 视为由有序部分 $A[1\ldots i-1]$ 和无序部分 $A[i\ldots n]$ 组成。\n初始化时，在有序区域仅存有第一个元素，在无序区域则包含剩余的 $n-1$ 个元素。\n每次操作均取当前无序区的第一个记录项 $A[i]$ .\n然后将其恰当地插入到当前有序区域中的适当位置。\n经过这样的操作共需 $n-2$ 次即可完成整个排序过程。\n

算法伪代码

INSERTION-SORT(A,n)

复制代码

      for  j←2 to n
     2.           do  key←A[j]
     3.           i←j-1
     4.           while i>0 and A[j]>key
     5.                    do A[i+1]←A[i]
     6.                   i←i-1
     7.          A[i+1]=key

算法时间复杂度的分析

对应行的代价	次数
c1	n
c2	n-1
c3	n-1
c4	∑t(j)
c5	∑(t(j)-1)
c6	∑(t(j)-1)
c7	n-1

由此可得 $T(n)$ 等于 $c_1$ 至 $c_7$ 各项之和；在同一个序列中

全部评论 (0)

还没有任何评论哟~