数据结构-插入排序-表插入排序

插入排序：

①直接插入排序。

②折半插入排序。

③2-路插入排序。

④表插入排序。←this

⑤希尔排序。

表插入排序，用表的方式进行插入排序操作

描述过程：将一个记录插入到已排好序的有序表中，

优点：避免了移动

时间复杂度：O(n2)

const int SIZE=10; typedef struct{ int rc;//记录项 int next;//指针项 }SLNode; typedef struct{ SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 }SLinkListType; //静态链表类型 void Arrange(SLinikListType &SL){ int p = SL.r[0].next; // p指示第一个记录的当前位置 for(int i=1;i<SL.length;++i){ while(p<i) p=SL.r[p].next; q = SL.r[p].next; if(p!=i){ SL.r[p]←→SL.r[i]; SL.r[i].next = p; } p = q; } }//Arrange