插入排序之四 表插入排序

Admin

  若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。存储结构定义如下：

1. #define SIZE 100        //静态链表容量
   
2. typedef struct  
   
3. {
   
4.     string rc;        //记录项
   
5.     int next;        //指针项
   
6. }SLNode;                //表结点类型
   
7. typedef struct
   
8. {
   
9.     SLNode r[SIZE];    //0号单元为表头结点
   
10.     int length;        //链表当前长度
    
11. }SLinkListType;        //静态链表类型

复制代码

为了方便插入，设数组中下标为“0”的分量为表头结点，并令表头结点记录的关键字取最大整数MAXINT。则表插入排序的过程描述如下：首先将静态链表中数组下标为“1”的分量（结点）和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记录关键字非递减有序插入到循环链表中。时间复杂度为O(n^2)。理解：和直接插入排序同样的处理方式，只不过不需要移动记录，只要改变next域。表插入排序的结果只是求得一个有序链表，所以只能进行顺序查找。

算法同直接插入排序。

xywv1

好好好好好好好好好好