vlambda博客
学习文章列表

前面介绍了已经介绍了三种排序，暴力排序、冒泡排序和简单选择排序，一个共同点都是基于交换。

我们可以用另一种视角来看待排序，即将一个待排序的数组看成两个部分：有序区和乱序区。

在排序开始前，整个数组都是乱序区，而有序区则为空：

排序开始后，有序区逐渐扩大，乱序区逐渐缩小：

排序完成后，整个数组都是有序区，乱序区则为空：

核心思想：将数组看作无序区和有序区两个区，从无序区中选出一个元素，按大小插入到有序区的合适位置。当无序区为空时，有序区自然就完成排序了。

动态过程如下：

Play

代码实现如下：

/*
 * 直接插入排序
 * array : 数组
 * length : 数组长度 
 */
void straight_insertion_sort(int *array, int length)
{
    int i, j;
    // 外层循环 决定待插入值
    for (i = 1; i < length; i++) {
        if (array[i] < array[i - 1]) {
            int tmp = array[i]; // 待插入值
            // 内层循环 在有序区中为待插入值腾出位置
            for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp; // 插入
        }
    }
}

请注意插入元素到有序区的关键代码 array[j + 1] = tmp;中的 j+1。

以上就是直接插入排序的基本原理。

完整代码请移步至 GitHub^[1] | Gitee^[2] 获取。

如有错误，还请指正。

推荐阅读

参考资料