链表插入排序示例 初始 index:(0):(1):(2):(3):(4):(5):(6) key MaxNum:21:25:49:25}16:08 状态link:1 0;0;0;0 2key: MaxNum:21:25:49:25:1608 link 0:0:0 i=3key: MaxNum:21:25:49:25:16:08 link 2:3:0:0:0:0 i=4kegy: MaxNun:2125:49:25:16:08 link 2;4:0;3 =5key; Max Num:21:25:49:25:16:08 link 5 2:4:0:3 i=6kegy: MaxNun:2l:25:49:25:1608 link 2:4:0;3:1:5
初始 index (0) (1) (2) (3) (4) (5) (6) key MaxNum 21 25 49 25* 16 08 状态 link 1 0 0 0 0 0 0 i＝2 key MaxNum 21 25 49 25* 16 08 link 1 2 0 0 0 0 0 i＝3 key MaxNum 21 25 49 25* 16 08 link 1 2 3 0 0 0 0 i＝4 key MaxNum 21 25 49 25* 16 08 link 1 2 4 0 3 0 0 i＝5 key MaxNum 21 25 49 25* 16 08 link 5 2 4 0 3 1 0 i＝6 key MaxNum 21 25 49 25* 16 08 link 6 2 4 0 3 1 5 链表插入排序示例
用于链表排序的静态链表的类定义 template <class Type> class staticlinklist; template <class Type> class Element i private Type key;/结点的关键码 int link. 结点的链接指针 publi Element(: key(0), link(nullf Type getKey(){ return key;}/提取关键码 void setKey( const Type x){key=x;}∥修改 int getLink(f return link;) /提是取链指针 void setlink( const int l){limk=l;}∥设置指针
用于链表排序的静态链表的类定义 template <class Type> class staticlinklist; template <class Type> class Element { private: Type key; //结点的关键码 int link; //结点的链接指针 public: Element ( ) : key(0), link (NULL) { } Type getKey ( ) { return key; } //提取关键码 void setKey ( const Type x ) { key = x; } //修改 int getLink ( ) { return link; } //提取链指针 void setLink ( const int l ) { link = l; } //设置指针
template <class Type> class staticlinklist st i public dstaticlinklist( int Max sz- DefaultSize ) Max size( Maxsz), Currentsize(O)/构造函数 i Vector=new Element <Type> [Maxsz]; j private: Element <Type> s vectors 存储向量 int max size. Currentsize /向量中最大元素个数和当前元素个数
} template <class Type> class staticlinklist { public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) //构造函数 { Vector = new Element <Type> [MaxSz]; } private: Element <Type> * Vector; //存储向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 }
链表插入排序的算法 template <class Type> int LinkInsertsort( staticlinklis<Type>& list)i list. Vector[O]. setKey( MaxNum); list. Vector[o]. setLink( 1); lis.ecor[] setlink(0);/形成循环链表 for( int i=2; i<=list. CurrentSize; i++)t intint current= list. Vector[0].getLink( int pre =0; 前驱指针 while( list. VectorlcurrentgetKey( lis.ecor{] getKey(){∥找插入位置 pre= current;1pre跟上 g current 向前走 current=list. Vector[current].getlink (:
链表插入排序的算法 template <class Type> int LinkInsertSort ( staticlinklis<Type> & list ) { list.Vector[0].setKey ( MaxNum ); list.Vector[0].setLink ( 1 ); list.Vector[1].setLink ( 0 ); //形成循环链表 for ( int i = 2; i <= list.CurrentSize;i++ ) { int int current = list.Vector[0].getLink ( ); int pre = 0; //前驱指针 while ( list.Vector[current].getKey ( ) <= list.Vector[i].getKey ( ) ) { //找插入位置 pre = current; //pre跟上, current向前走 current = list.Vector[current].getLink ( ); }
list. Vector[i]. setLink( current ) list. Vectorlpre] setLink(i); 在prl与 curren之间链入 算法分析 使用链表插入排序,每插入一个对象,最大 关键码比较次数等于链表中已排好序的对象 个数,最小关键码比较次数为1。故总的关键 码比较次数最小为n-1,最大为 n(n 1)
算法分析 使用链表插入排序，每插入一个对象，最大 关键码比较次数等于链表中已排好序的对象 个数，最小关键码比较次数为1。故总的关键 码比较次数最小为 n-1，最大为 list.Vector[i].setLink ( current ); list.Vector[pre].setLink ( i ); //在pre与current之间链入 } } 2 ( 1) 1 1 − = − = n n i n i