链表插入排序 基本思想是:在每个对象的结点中增加一个 链接指针数据成员ink。 对于数组中的一组对象v1l,…,vm,若 VIl,…V[1已经通过指针ink按其排序 码从小到大链接起来。现要插入V[i=2, 3,,n,则必须在前面i1个链接起来的对象 当中,循链检测比较,找到V应插入的位置 把V链入,并修改相应链接指针。从而得到 VIl,灬…,v的一个通过指针排好的链表。 如此重复执行,直到把Ⅴm也插入到链表中 排好序为止
链表插入排序 ◼ 基本思想是：在每个对象的结点中增加一个 链接指针数据成员 link。 ◼ 对于数组中的一组对象V[1], …, V[n], 若 V[1], …, V[i-1]已经通过指针link, 按其排序 码从小到大链接起来。现要插入V[i], i = 2, 3, …, n, 则必须在前面i-1个链接起来的对象 当中, 循链检测比较, 找到 V[i] 应插入的位置， 把V[i] 链入, 并修改相应链接指针。从而得到 V[1], …, V[i]的一个通过指针排好的链表。 ◼ 如此重复执行，直到把V[n]也插入到链表中 排好序为止
2125 49 d 08 0 2 3 初始 i=2 current pre i i=3■ current pre pre current
25 49 25* 16 08 0 1 2 3 4 5 6 i = 2 i = 3 21 初始 current pre i current pre i pre current i i = 4
2125 49 d 08 0 2 3 i=5 pre current i=6 current 结果口
25 49 25* 16 08 0 1 2 3 4 5 6 i = 5 i = 6 21 pre current i 结果 pre current i
用于链表排序的静态链表的类定义 template <class Type> class staticlinklist; template <class Type> class Element i private Type key;∥结点的排序码 int link: 结点的链接指针 public Element (: key(O), link (NULD Type getKey(i return key; void setKey( const Type x ) key=x;) int getLink(f return link;) void setlink( const int 1) link=1;j
用于链表排序的静态链表的类定义 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 t p rivate Element<ype>* Vector;∥存储向量 int MaxSize Currentsize /向量中最大元素个数和当前元素个数 public dstaticlinklist( int MaxSz= Defaultsize MaxSize( maxsz ) Currentsize(0) i Vector= new Element <Type> []; j
} template <class Type> class staticlinklist { private: Element <Type> * Vector; //存储向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; } }