链表插入排序的算法 template <class Type> int staticlinklis<Type>:: LinkedIns Sort(& Vector. key- MaxNum; Vector[O]. link=1; Vector[1].link =0; ∥素V0与V形成循环链表 for( int i=2; 1<=CurrentSize; 1++)i int current= Vector[O]. link;/检测指针 int pre =0; 检测指针的前驱指针 while( vector[current].key s Vector[]. key i ∥/插入位置 pre= current;/pre跟上, current向前走
链表插入排序的算法 template <class Type> int staticlinklis<Type> :: LinkedInsSort ( ) { Vector[0].key = MaxNum; Vector[0].link = 1; Vector[1].link = 0; //元素V[0]与V[1]形成循环链表 for ( int i = 2; i <= CurrentSize; i++ ) { int current = Vector[0].link; //检测指针 int pre = 0; //检测指针的前驱指针 while ( Vector[current].key <= Vector[i].key ) { //找插入位置 pre = current; //pre跟上, current向前走
current- Vector current. link: Vector[]. link- current; Vector lpre]. link=i; 在pre与 current-之间链入 使用链表插入排序,每插入一个对象,最大排 序码比较次数等于链表中已排好序的对象个 数,最小排序码比较次数为1。故总的排序码 比较次数最小为n-1,最大为只.n(n-1) 2
◼ 使用链表插入排序, 每插入一个对象, 最大排 序码比较次数等于链表中已排好序的对象个 数, 最小排序码比较次数为1。故总的排序码 比较次数最小为 n-1，最大为 current = Vector[current].link; } Vector[i].link = current; Vector[pre].link = i; //在pre与current之间链入 } } 2 ( 1) 1 1 − = − = n n i n i
用链表插入排序时,对象移动次数为0。但为 了实现链表插入,在每个对象中增加了一个 链域link,并使用了 Vector0作为链表的表 头结点,用了n个附加域和一个附加对象。 算法在 Vectorlpre]key= Vector[ikey时将 Vector插在 Vectorlpre的后面,所以,链表 插入排序方法是稳定的
◼ 用链表插入排序时, 对象移动次数为0。但为 了实现链表插入, 在每个对象中增加了一个 链域 link, 并使用了Vector[0] 作为链表的表 头结点, 用了 n 个附加域和一个附加对象。 ◼ 算法在Vector[pre].key == Vector[i].key时,将 Vector[i]插在Vector[pre]的后面, 所以, 链表 插入排序方法是稳定的
希尔排序( Shell sort) 希尔排序方法又称为缩小增量排序。该方法 的基本思想是:设待排序对象序列有n个对 象,首先取一个整数gap<n作为间隔,将全 部对象分为gap个子序列,所有距离为gap 的对象放在同一个子序列中,在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap,例如取gap=gap/21,重复上述的子序 列划分和排序工作。直到最后取gap==1, 将所有对象放在同一个序列中排序为止
希尔排序 (Shell Sort) ◼ 希尔排序方法又称为缩小增量排序。该方法 的基本思想是 : 设待排序对象序列有 n 个对 象, 首先取一个整数 gap < n 作为间隔, 将全 部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序 列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序 列划分和排序工作。直到最后取gap == 1, 将所有对象放在同一个序列中排序为止
49 25416 08 0 2 Gap=3 同 日r
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