排序-插入排序-表插入排序

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];
    }
}

---

三、时间复杂度

表插入排序仅仅是将移动元素的操作由n²数量级降低到了n数量级，但是可以看到查找插入位置这一操作仍旧是n²数量级，所以时间复杂度依旧是O(n²)

---

参考文档：
[1] [数据结构C语言版 -- 清华大学出版社]