用链表插入排序时,对象移动次数为0。但为 了实现链表插入,在每个对象中增加了一个链 域link,并使用了 vector0作为链表的表头结点, 总共用了n个附加域和一个附加对象。 算法从i=2开始,从前向后插入。并且在 vectorlcurrent Key== vector[i]. Key f,current 还要向前走一步,pre跟到 current原来的位置, 此时, vectorlpre Key= vector.Key将 vector插在 vectorlprel的后面,所以,链表插 入排序方法是稳定的
希尔排序( Shell sort) 希尔排序方法又称为缩小增量排序。该方法的 基本思想是:设待排序对象序列有n个对象, 首先取一个整数gp<n作为间隔,将全部对 象分为gqp个子序列,所有距离为gqp的对象 放在同一个子序列中,在每一个子序列中分别 施行直接插入排序。然后缩小间隔gqp,例如 取gqp=「sqp/2,重复上述的子序列划分和排 序工作。直到最后取gp==1,将所有对象放 在同一个序列中排序为止
21 2549 25116 [o8 2 3 5 Gap =3 21 25 25 16
0 1 2 3 4 5 49 25 16 08 49 25* 08 21 21 25 25* 16
49 2116 25125 03 2 3 5 Gap=2 21 25 同目 49 16
0 1 2 3 4 5 49 16 25* 08 21 25
1621-2525 49 08 2 3 i=3 5 Gap=l 08(162125 25 49 开始时gq的值较大,子序列中的对象较少 排序速度较快;随着排序进展,gqp值逐渐变 小,子序列中对象个数逐渐变多,由于前面 工作的基础,大多数对象已基本有序,所以 排序速度仍然很快
0 1 2 3 4 5