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