statement：本篇内容只是建立在我目前经验的基础之上，必然有不完善甚至是不正确的地方，请谨慎阅读，如果能指出错误与不足之处，更是不甚感激
PS1：代码部分将使用Java语言进行展示
PS2：本节排序算法基于顺序表排序
一、原理
- 表插入排序旨在更进一步降低顺序表插入后移动元素的操作时间，故启用了一种静态链表的方案（即使用另外一组数组记录下待排序数组每个元素下一元素的下标），使用静态链表后，就不再需要移动元素了，只需要更改父节点和待插入节点的对应的“next节点”值即可。
二、代码
- Java代码
public static void staticLinkInsertSortASC(int[] sortArray) {
int[] indexList = new int[sortArray.length]; //sortArray的静态索引序列
int[] resultList = new int[sortArray.length];//用于记录静态链表遍历出来的结果
Arrays.fill(indexList, -1);//将数组中所有值初始化为-1
int minStart = 0;//头节点，最开始定为0
//排序
for(int i = 1 ; i < sortArray.length ; i++) {
int next = minStart;//下一个要比较的节点/索引
int last = -1;//上一个进行比较的节点/索引
while(sortArray[i] > sortArray[next]) {
last = next;
next = indexList[next];//获取下一个索引
if(next == -1) break;//如果下一个索引是-1，则说明到了链表尾部，待排序值为当前最大，退出循环
}
//插入链表
if(last == -1) {//如果上一个索引是-1，则说明待排序值是当前最小值，插入到链表最前端
minStart = i;
}else {
indexList[last] = i;
}
indexList[i] = next;
//System.out.println(Arrays.toString(indexList)+","+minStart);
}
//遍历有序静态索引序列indexList，生成对应的有序序列resultList
for(int i = 0 , next = minStart ; next != -1 ; next = indexList[next] , i++) {
resultList[i] = sortArray[next];
}
//替换sortArray的元素值
for(int i = 0 ; i < sortArray.length ; i++) {
sortArray[i] = resultList[i];
}
}
三、时间复杂度
表插入排序仅仅是将移动元素的操作由n2数量级降低到了n数量级，但是可以看到查找插入位置这一操作仍旧是n2数量级，所以时间复杂度依旧是O(n2)
参考文档：
[1] [数据结构C语言版 -- 清华大学出版社]
