常见的七种排序算法 ——直接插入排序

直接插入排序

在排序算法中，有七种是比较常见的：

1. 直接插入排序
2. 希尔排序（减小增量排序）
3. 选择排序
4. 堆排序
5. 冒泡排序
6. 快速排序
7. 归并排序

本篇博客，介绍的是 直接插入排序 的 思想，算法原理，算法实现。

观前须知：

1. 本篇博客是以 整数类型（int为例） 来进行介绍的，并不是说排序算法只能应用于 整数类型，排序算法是一种排序的思想，并不是只能限定于某一种 特定的类型数据 进行比较。
2. 排序中，默认都是 从小到大 进行排序。

1. 直接插入排序的思想

相信大家应该玩过扑克牌，当你拿到一张牌的时候，你是不是会惯性的去整理你手里的牌。

比如，将扑克牌按照从小到大的顺序，排序，整理好手中的牌。

那么，你整理牌的过程，就体现了 直接插入排序。

直接插入排序的算法，它的基本算法思想是什么呢？

算法基本思想

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

• 在待排序的元素中，假设前 n-1 个元素已有序（前提），现将第 n 个元素插入到前面已经排好的序列（数组）中，使得前 n个元素有序（目的）。按照此法对所有元素进行插入，直到整个序列（数组）有序。

图中的 i 代替了 n，所以 i - 1 就是 n - 1

大家看这个图，可能会很懵，没关系，大家看这个图，有个印象先。

为了大家看起来，某些概念不会太生硬，以下的文章内容，序列统统用 数组 来说。

2. 直接插入排序的算法原理

对于这个算法原理，我们需要用到另一种算法思想：双指针算法。

什么是双指针？如何使用双指针来解决题目？
这里有我写的一篇博客 —— 双指针_移动零，你可以看看。

对于直接插入排序，我个人总结了 3 步：
1. 比较插入前的准备工作
2. 比较，更换数组内元素的值，达到局部有序或完全有序
3. 对 待排序的序列 的 首个元素（也就是下标为 0 的元素），进行数值的更替。

2.1 比较插入前的准备工作

准备工作，我们要确定这么几件事：

1. 定义出中间变量，存放每一趟比较中，i所指向的值（因为在直接插入排序中，发生比较后，插入新数值时，i所指向的值是会被覆盖掉的）

中间变量，我以 tmp 为例。

int tmp = 0;

2. 确定 i 下标的起始位置和它的边界

i 所表示的是 比较的趟数，就是说：比较之后，数组内部发生值的更替，从而让 i-1 之前的数组内容达到有序的 次数。
i 所指向的数字，是本趟比较 待排序 的数字。

起始位置

先来看看，从 下标0 开始，是否合理？

所以，i 的起始位置，应该从 1下标 开始。

边界

对 待排序的数组 的每一个数字（除起始的第一个数字），都要进行一次与 i-1 及之前的所指向的数字（已排好序的数组）进行比较，排序。
所以，i 的边界，不能够超过 数组的最后一个元素的下标值，也就是说，i 可以指向到最后 一个数字的下标。
也就是 i < 数组长度（i < array.length）

可实现的代码：

所以现在我们可以写出这样的代码：

//        从 1 下标循环到数组的末尾，这是比较的趟数for (int i = 1; i < array.length; i++) {
//            中间变量指向 i 下标的值，也就是当前要进行排序，然后要插入有序数组中的值tmp = array[i];}

3. 确定 j 下标的起始位置和它的边界

j 所表示的是 本趟（i）比较，需要比较的次数。
j 下标所指向的数字，就是本趟比较中，与 被排序的数相比较的数，就是说：与被排序数（i 下标指向的数），之前已经排序好的数组中的每一个数（j 下标指向的数），进行比较大小，根据比较大小后的情况，在已排序好的数组中，进行值的更替。

起始位置

从上述文字可知，j 所指向的数字，是已经排序好的数组中的每一个数，又从直接插入排序的算法基本思想中可知，直接插入排序中，已排序好的数组的区间应该是：[ 0，i - 1 ] 。

所以，j 的起始位置应该是 已排序好数组的倒数第一个元素开始，从后往前 指向到 0下标的每一个数字，和 当前 i 所指向的数字（当前被排序数字）进行比较。

故，每一趟比较开始前，j 的起始位置为：i - 1。

边界

根据 已排序好的数组的区间应该是：[ 0，i - 1 ]
边界应该为： j >= 0

由于是从后往前，所以，j 每次比较完后，都要在原来的基础上，-1，指向 j 之前的一个元素
也就是：j – –

可实现的代码：

//        定义中间变量int tmp = 0;
//        从 1 下标循环到数组的末尾，这是比较的趟数for (int i = 1; i < array.length; i++) {
//            中间变量指向 i 下标的值，也就是当前要进行排序，然后要插入有序数组中的值tmp = array[i];
//            j 指向 i-1下标int j = i-1;
//            从 i-1开始，往前遍历，直到 j 走到 -1 位置，多次比较for (; j >= 0 ; j--) {//比较，更换数组内元素的值，达到局部有序或完全有序//......}}

2.2 比较，更换数组内元素的值，达到局部有序或完全有序

对于排序，可以分为以下两种情况进行讨论：

1. 数组中 j下标的值 > tmp的值（i下标的值）

我们举一个例子，先来看看，怎么个比较，然后交换的。

第一步：比较
第二部：更换数组内部元素的值，达到局部有序。
第三步：j 往前走一步

这时候，肯定会有心急的小伙伴问：那你 0 下标那个元素，怎么处理啊？ j 都已经到 -1 了，不满足循环的条件了，没机会更换 0 下标那个元素的值了。

对于这个问题，是下一个标题会讲到的内容，先往后看，了解完是如何比较，如何更换数组内部的值的思路吧~

如何在比较后，对数组内部的值进行更改

比较的规则很清晰，但是，更换数组内部的值，我们是怎么去更换的呢？规则是什么？
可以看到，我们这个图中，是将 j 下标的值，直接覆盖掉了 i 下标的值，那么，肯定就会有同学把 更换数组内部的值 的这一步代码，写成这样：array[i] = array[j]，那么，这一步的代码，写成这样，对吗？
答案：❌，这是不对的写法。

我们来看一个例子，就知道了。

可以看到，数组反而乱了，没有达到有序。

其实，我们真正想要的效果，是不是想要让 j 后面那个元素，被 5 覆盖掉。

那么 5 插入的位置是哪呢？

是不是就是 j 在没有 往前走 的情况下，j + 1 的位置（图中可知 j ：2 ，2(j)+1 == 3(被插入的 5 所在下标)）？

所以，我们在更改数组内部的值的这一步的代码，应该是这样的：array[j + 1] = array[j]。

所以，这就是我们在 数组中 j下标的值 > tmp的值（i下标的值）这种比较结果的情况下，对数组内部值的更改的正确代码，这一步非常重要！！！

2. 数组中 j下标的值 < tmp的值（i下标的值）

对于这种结果，我们先来看图，看看图中的例子：

对于这种比较的结果，我们应该要执行什么样的操作呢？

我们先来分析分析：

1. 图中，[ 0，3 ] 这个区间的数字，满足了有序（从小到大）
2. 满足有序的数组的倒数第一个下标是 3，它（3） 等于（==）i - 1，符合我们算法基本思路中： “前 n（i）-1 个元素已有序” 。

所以，既然已经满足了有序，且符合 “前 n（i）-1 个元素已有序”，这个条件了，那么，我们是不是应该结束本趟的比较？
答案：✔

但是，在结束本趟比较之前，我们还需要做一件事，就是要将
j + 1 下标的值，进行更改，更改什么呢？
答：tmp 中的值。array[j + 1] = tmp;

只有这样，才能完成 本趟 比较 想要达到的效果：达到有序。

可实现的代码：

//      如果数组j下标的值 > tmp的值，就将数组 j+1 下标的值，改成 当前j下标所表示的值，也就是往后移动。if(array[j] > tmp){array[j + 1] = array[j];
//如果数组j下标的值 < tmp的值，说明该数组，j下标以及j下标之前的数，已经有序了，}else {
//此时，直接将tmp里面所表示的值，放到j + 1下标处，即插入成功了。同时结束循环array[j + 1] = tmp;break;}

结合 第一，二步，可实现的代码：

//        定义中间变量int tmp = 0;
//        从 1 下标循环到数组的末尾，这是比较的趟数for (int i = 1; i < array.length; i++) {
//            中间变量指向 i 下标的值，也就是当前要进行排序，然后要插入有序数组中的值tmp = array[i];
//            j 指向 i-1下标int j = i-1;
//            从 i-1开始，往前遍历，直到 j 走到 -1 位置，多次比较for (; j >= 0 ; j--) {
//      如果数组j下标的值 > tmp的值，就将数组 j+1 下标的值，改成 当前j下标所表示的值，也就是往后移动。if(array[j] > tmp){array[j + 1] = array[j];
//如果数组j下标的值 < tmp的值，说明该数组，j下标以及j下标之前的数，已经有序了，}else {
//此时，直接将tmp里面所表示的值，放到j + 1下标处，即插入成功了。同时结束循环array[j + 1] = tmp;break;}}
//对 待排序的序列 的 首个元素（也就是下标为 0 的元素），进行数值的更替。
//................}

2.3 对 待排序的数组 的 首个元素（也就是下标为 0 的元素），进行数值的更替。

我们在 2.2标题中，第一种比较情况（ 数组中 j下标的值 > tmp的值（i下标的值））中，遗留了一个问题：

问题：更换数组内部的值以后，0 下标那个元素，怎么处理啊？ j 都已经到 -1 了，不满足循环的条件了，没机会更换 0 下标那个元素的值了。

首先，我们来分析一下图中的情况：

1. 这张图里面，i 指向的下标是 1 ，也就是说，本趟排序，我们希望将 i 以及 i 之前的数，到达有序。
2. 在 i 及 i 之前的数，恰好 i 指向的 5 ，是这个区间[ 0，i ]中最小的数。
3. j + 1 下标的值已经发生了更改，同时 j 下标 也已经往前走，走到了 -1 下标，无法进入循环，比较并更换数组内元素的值了

根据分析，我们可以得出这样一个结论：
当 i 当前指向的这个 待排序数 ，是 i 以及 i 之前的区间数组中，是最小的数时，会发生这么一种情况：
本趟排序完成后，数组的首个元素的值，没有更改为最小值。

所以，我们需要解决这么一个问题：当 i 指向的值时最小的数时，排序结束，我们应该要将元素的首个元素，更改为tmp中存放的值（tmp存放的是当前 i 指向的值）。

我们代码要怎么来写呢？再来看看图片：

如何定位到首个元素呢？数组首个元素不是 0 下标吗？
直接 array[0] = tmp;可不可以呢？
答：肯定不行，不严谨。

可以看到，图中 j 下标的值为 -1 ，我们让 j + 1，就可以等于 0了。即array[j + 1] = tmp;

解决这个问题，我们可以有两种写法：

1. 带判断，只作用于 i 指向的是最小值 的情况

当 i 指向的是最小值 的时候，本趟排序结束后， j 的值为 -1。

所以，当 j == -1 的时候，我们再执行这条句子array[j + 1] = tmp;

代码：

//            最后，需要在当前这次比较完成后，判断 j 的下标是否为 -1
if (j == -1){array[j + 1] = tmp;
}

2. 不带判断，每一趟比较完成后，都让 j + 1 位置的值赋值为 tmp中存放的值

代码：

//            最后，需要在当前这次比较完成后，重值 j + 1 下标位置的值
array[j + 1] = tmp;

这种方式是什么意思呢？
我们来看图：

图中显示的是：本趟比较，是因为已经有序了，达到 break 语句，提前结束了，所以 j 是没有 -1 的，还是指向 2 下标的位置。

所以执行这条语句：array[j + 1] = tmp;，也仅仅是把 3 下标的值，又赋值了一遍而已，相当于 break 语句前的array[j + 1] = tmp;，执行了两次，对数组内部的值，没有改变。

再来看 i 指向的是最小值 的情况：

不加判断的情况下，array[j + 1] = tmp;也可以将 数组的首个元素，更改为 最小值。

总结：

这两种方式的代码，你随便选就可以，都能达到最终目的：将数组的首个元素，更改为最小值。

3. 完整代码（带注释）

//直接插入排序算法://时间复杂度：
//考虑最坏情况下：5，4，3，2，1，每一次，都要比较 i 次，总共比较 1+2+3+4+...+n-1 次
//等差数列求和后得：O(N^2)
//
//空间复杂度：O(1)，因为并没有申请多余的数组，有的只是常数个变量//稳定性：是稳定的排序//传入的数组越接近有序，直接插入排序的算法时间效率越高//直接插入排序算法的核心思想：
//    首先，让 i 指向 数组的 1下标元素，因为 0下标元素单个，默认是有序的
//    定义另一个 指针j，指向 i-1下标的元素。   多趟循环（i），多次比较（j）
//将数组i下标的元素，放到中间变量 tmp中，让tmp存储的值和数组j下标的元素进行比较。//比较的过程：让 j 下标从 i-1 到 -1，依次遍历数组，与 tmp 比较每一个下标的值
//如果数组j下标的值 > tmp的值，就将数组 j+1 下标的值，改成 当前j下标所表示的值，也就是往后移动。
//如果数组j下标的值 < tmp的值，说明该数组，j下标以及j下标之前的数，已经有序了，
//此时，直接将tmp里面所表示的值，放到j + 1下标处，即插入成功了。同时结束循环//    最后，需要在当前这次比较完成后，判断 j 的下标是否为 -1。
//因为当 i下标 所指向的值，是整个数组最小的时候，j走到0下标后，将 j+1下标的值更改为 j下标的值后，j--，j为 -1，结束循环
//此时，tmp的值，并没有插入数组（也就是没有执行 array[j + 1] = tmp 这条语句），
// 所以，当 j == -1 时，表示当前i下标的元素，是最小的元素，需要放到数组的 0 下标
//而 当j == -1，array[j + 1] = tmp，就是把最小的元素，放到了 0下标。public static void func_insertSort_1(int[] array){
//        定义中间变量int tmp = 0;
//        从 1 下标循环到数组的末尾，这是比较的趟数for (int i = 1; i < array.length; i++) {
//            中间变量指向 i 下标的值，也就是当前要进行插入的值tmp = array[i];
//            j 指向 i-1下标int j = i-1;
//            从 i-1开始，往前遍历，走到 -1 位置，多次比较for (; j >= 0 ; j--) {
//      如果数组j下标的值 > tmp的值，就将数组 j+1 下标的值，改成 当前j下标所表示的值，也就是往后移动。if(array[j] > tmp){array[j + 1] = array[j];
//如果数组j下标的值 < tmp的值，说明该数组，j下标以及j下标之前的数，已经有序了，}else {
//此时，直接将tmp里面所表示的值，放到j + 1下标处，即插入成功了。同时结束循环array[j + 1] = tmp;break;}}
//            最后，需要在当前这次比较完成后，判断 j 的下标是否为 -1if (j == -1){array[j + 1] = tmp;}//array[j + 1] = tmp;}
}