排序-插入排序-直接插入排序

statement：本篇内容只是建立在我目前经验的基础之上，必然有不完善甚至是不正确的地方，请谨慎阅读，如果能指出错误与不足之处，更是不甚感激
PS1：代码部分将使用Java语言进行展示
PS2：本节排序算法基于顺序表排序

---

一、原理

• 把一个待排序的元素插入到一个已经有顺序的序列（使用时可以把第一个元素看成是有序的）之中（寻找插入点的过程是一个直接的遍历对比的过程，故称为“直接”插入排序）
• 假设待排序队列长度为length，简单可知，上述过程需要进行length-1次，顺序表的话，还有一步将其他元素向后移动的操作

---

二、代码

• Java代码

public static void simpleInsertSortASC(int[] sortArray) {
    for(int i = 1 ; i < sortArray.length ; i++) {//循环length-1次
        int j = i;
        int temp = sortArray[i];//记录下要插入的元素
        for(;j > 0 && temp < sortArray[j-1]; j--) {
            //检测要插入的元素是否大于索引j-1指向的元素，如果大于则在j处插入，如果小于则将j-1处的元素向后移动
            sortArray[j] = sortArray[j-1];
        }
        sortArray[j] = temp;
        //System.out.println(Arrays.toString(sortArray));
    }
}

• C代码

void simpleInsertSortASC(int *sortArray){
    //这里的数组0号元素存储的是数组长度
    for(int i = 2 ; i <= sortArray[0] ; i++) {
        int j = i;
        int temp = sortArray[i];
        for(; j > 0 && temp < sortArray[j-1] ; j--){
            sortArray[j] = sortArray[j-1];
        }
        sortArray[j] = temp;
    }
}

---

三、时间复杂度

最差的情况是完全逆序的情况，大概可知时间复杂度是O(n²)

---

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