7.4 插入排序——直接插入排序

插入排序基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想。

直接插入排序

当插入第$i(i\ge 1)$个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

如下面动图所示：

以及这个样例：

8
36 25 48 12 65 43 20 58
第0步:[36] 25 48 12 65 43 20 58
第1步:[25 36] 48 12 65 43 20 58
第2步:[25 36 48] 12 65 43 20 58
第3步:[12 25 36 48] 65 43 20 58
第4步:[12 25 36 48 65] 43 20 58
第5步:[12 25 36 43 48 65] 20 58
第6步:[12 20 25 36 43 48 65] 58
第7步:[12 20 25 36 43 48 58 65]

根据分析的信息，给出两种参考程序，他们的思路是一样的。

参考程序

参考程序1：

void insertSort(int* a, int n) {for (int i = 0, j, k, temp; i < n; i++) {for (j = i - 1; j >= 0; j--)if (a[j] < a[i])//修改这里的比较运算符为<=能使算法不稳定break;if (j != i - 1) {temp = a[i];for (k = i - 1; k > j; k--)a[k + 1] = a[k];a[k + 1] = temp;}}
}

参考程序2：

void InsertSort(int* a, int n) {for (int i = 0; i < n - 1; ++i) {// [0, end] 有序，插入tmp依旧有序int end = i;//int end;表示单趟，int end=i;和for表示整个过程int tmp = a[i + 1];while (end >= 0) {if (a[end] > tmp) {//修改这里的比较运算符为>=能使算法不稳定a[end + 1] = a[end];--end;}elsebreak;}a[end + 1] = tmp;}
}

直接插入排序的特性总结

1. 元素集合越接近有序，直接插入算法>排序算法的时间效率越高

2. 时间复杂度：$O(N^2)$（两层for循环，尽管存在剪枝但不影响整体效率低）

3. 空间复杂度：$O(1)$，

4. 它是一种稳定的算法>排序算法，因为在排序过程中，它是将未排序元素插入到已排序序列的合适位置。尽管我们能通过修改判断关键字大小的判断原理来使得它不稳定，但不影响这种交换机制使得直接插入排序是稳定的。