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