链表插入排序示例 初始 index( (1)(2)(3)(4)(5)(6 key MaxNu212549251608 状态link 0000 0 =2 key MaxNum212549251608 link 200000 =3 key MaxNum 21 25 49 25 16 08 link 300 0 0 i=4 key MaxNur212549251608 link 240300 i=5 key MaxNum 21 25 49 25 16 08 link 5 2403 10 i=6 key MaxNun212549251608 link 6 240315
初始 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;∥结点的链接指针 public Element(: keyO), link(Nulli ype getkey(){ return keys;}∥提取关键码 void setKey( const Type x){key=x;}∥修改 int getLink(){ return link;}∥提取链指针 void setlink( const int l){lmk=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 public: dstaticlinklist(int MaxSz= DefaultSize): Max Size( Marsz), Currentsize(0)∥构造函数 i Vector new Element <Type> [MaxSz]; private Element <Type> s vector, ∥存储向量 int MaxSize, 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 )3 list. Vector[O]. setLink( 1); list. vector[]. etlink(0);∥形成循环链表 for ( int i=2; i<= list. CurrentSize; i++)& int int current=list. Vector[O].getLink o; int pre =0; ∥前驱指针 while( list. Vector[current].getKey o<- list, Vector[引 getKey()){∥找插入位置 pre= current;pre跟上, current向前走 current=list. Vector[current] getLink (;3
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 )3 list. Vectorlpre] setLink (i ) ∥在pre与 current之间链入 算法分析 使用链表插入排序,每插入一个对象,最大 关键码比较次数等于链表中已排好序的对象 个数,最小关键码比较次数为1。故总的关键 码比较次数最小为n-1,最大为 n(n-1)
list.Vector[i].setLink ( current ); list.Vector[pre].setLink ( i ); //在pre与current之间链入 } } 2 ( 1) 1 1 n n i n i