数据结构 - 直接插入排序法

ゝ一纸荒年。 2022-07-11 14:08 222阅读 0赞

# 数据结构 - 直接插入排序法。 #

之前的博文已经介绍了 [冒泡排序法][Link 1]  
和 [简单选择排序法][Link 2].

其实上面两种的基本思路是一样的， 就是通过两层循环， 在每1个内循环中找到1个未排序的极值元素， 然后把这个元素移动到数组前列。

但是这篇文章介绍的 直接插入排序法 的基本思路则与上面的排序方法不同， 而且可以讲 直接插入排序法 的算法更加直接人类大脑的思路。

## 基本思路 ##

### 一个例子 ###

假设我们面前有几张牌

|1|2|3|7|6|5|9|8|

要让你移动牌的位置， 让这些牌从小到达重新排列。

让我们模拟你的大脑行为…

首先， 我们一样就看出前面的|1|2|3|是排好序的， 不需要比较和移动。

其次， 我们不会去考虑剩下未排序中的牌哪张是最小的。

而是会去观察， 咦？ 发现6比7大窝～

就去将牌6 放到 7的前面， 牌就变成这样了：

|1|2|3|6|7|5|9|8|

然后继续， 又发现5比7小， 就把5放到前面， 放到哪个牌前面呢， 直觉上我们会觉得6比5大， 所以放在6 前面：

|1|2|3|5|6|7|9|8|

下一步， 我们发现9比7大…不移动， 而是把后面的8移动到9前面。

|1|2|3|5|6|7|8|9|

好了， 区区几步就完成了排序， 是不是觉得我们的大脑很强大？

### 思路分析 ###

但是， 如果我们要用代码去模拟我们大脑的算法，就必须了解清楚这个算法的每1个步骤细节。

#### 1.确定开始比较的牌 ####

首先， 我们一开始就跳过了1 2 3 这3张牌， 直接去比较后面那两张牌7和5。  
是因为我们觉得前面的123 已经拍好序了。

但是前面存在若干个排好序的元素是这个排序方法的前置条件吗？

不是的，

假如我们去掉牌123， 变成如下这样子:

|7|6|5|9|8|

还是可以用这个思路来排序的。 因为我们可以当第1个元素7， 把它当成1个已经排好序的队列.

所以， 实际比较是从队列第二张牌6开始的。

也就是将， 这个思路中， 如果有1个数组 arr\[n\], 比较从第二个元素arr\[1\]

#### 2.跟谁比较 ####

接下来继续讲， 我们拿牌6 来 比较了，跟谁比较呢， 是跟6前面的牌7来比较。

也就是讲， 如果我们比较的元素是arr\[i\], 那么会跟它前面的元素arr\[i-1\]来比较。

#### 3.如果arr\[i\] 比 arr\[i-1\] 大 ####

为了方便表述我们把数组改成如下这个状态

|1|2|3|6|7|5|9|8|

我们正在比较的元素是7， 发现7比6小的情况下， 是不会移动任何牌的位置的， 而是去比较一下张牌5.

也即是将， 如果arr\[i\] > arr\[i-1\]的话， 直接i++ 去较下一张牌

#### 4.相反，如果arr\[i\] 比 arr\[i-1\] 小 ####

现在我们比较的是5 和 它前一位的7

|1|2|3|6|7|5|9|8|

这种情况下就要改变 元素的位置了。  
我们会把牌5往前面放， 但是放在哪里呢， 而且怎么放呢。 还继续要分析

#### 5. 先把要前移的牌拿出来 ####

队列就变成这样子

|1|2|3|6|7|\*|9|8|

|5|

#### 6. 前面的牌往后一1个位置。 ####

实际上， 5前面的 6和7 都要往后移动1个位置， 为什么3不移动呢， 因为3比5小啊

分两步（实际上是1个循环）

|1|2|3|6|7|\*|9|8| ==>

|1|2|3|6|\*|7|9|8| ==>

|1|2|3|\*|6|7|9|8|

#### 7. 拿出来的牌放回去 ####

|1|2|3|5|6|7|9|8|

#### 8. 继续比较下一张牌 ####

|1|2|3|5|6|7|9|8|

#### 9.小结 ####

可以看出， 这个算法还是有两个循环的。

外循环用于比较元素和它前1个元素。

内循环实际上是移动1个子队列。

## 代码实现 ##

了解思路后， 用c语言写下代码是不难的

int straightInsertionSort(int * arr, int len){
        int i, j;
        int tmp = 0;
        for (int i = 1; i < len; i++){
            if (arr[i-1] > arr[i]){ //1. the element will be moved only if it's smaller then the previous one
                                    //2. the element only will be moved forward.
                tmp = arr[i]; //use a variable to store the element which will be moved.
                j = i - 1;
                do {
                    arr[j + 1] = arr[j];         //move the previous element one position backward fisrt;
                    j--;
                }
                while (j >= 0 && arr[j] > tmp);  // all the elements after the new position of the moving element move!
    
                arr[j + 1] = tmp;                //put the moving element to the new position
            }
        }
        return 0;
    }

## debug信息 ##

我们来看下 debug信息

4, 1, 5, 8, 0, 3, 7, 9, 6, 2
    *1, 4, 5, 8, 0, 3, 7, 9, 6, 2
    *0, 1, 4, 5, 8, 3, 7, 9, 6, 2
    0, 1, *3, 4, 5, 8, 7, 9, 6, 2
    0, 1, 3, 4, 5, *7, 8, 9, 6, 2
    0, 1, 3, 4, 5, *6, 7, 8, 9, 2
    0, 1, *2, 3, 4, 5, 6, 7, 8, 9
    change count: 25
    compare count: 22
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9

可以看出元素是怎样被移动的。  
这个算法比较了20次， 位置移动了25次

首先， 这个算法比较次数相当少， 同1个数组， 用冒泡排序法的比较次数是39哦， 而简单选择法的比较次数是45.

位置移动是25, 跟冒泡还多吗。

不， 冒泡的位置改动实际上是元素交换(移动两个元素)， 而这里的位置改动真的是1个元素的位置改动！

可以看出， 直接插入选择法比冒泡排序法具有更高的效率。  
实际上， 比起简单选择法也是更好的

## 时间复杂度分析。 ##

首先 最好的情况， 就是已经排好序的， 只需要比较n次， 无任何元素移动, 时间复杂度是O(n)

但是， 最坏打情况下的话

就是， 数组本身是按倒序排列的例如

|5|4|3|2|1|

那么， 比较次数是  
∑*i*=1*n*−1*i*=1\+2\+3\+4\+...\+*n*−1=*n*(*n*−1)2

移动次数是  
∑*i*=2*n*−1*i*=2\+3\+4\+...\+*n*=*n*(*n*\+2)2