排序 - 插入排序 [1 - 直接插入排序]

布满荆棘的人生 2022-01-14 01:34 350阅读 0赞

在这篇文章中，你将看到最容易理解的一种排序方法：直接插入排序。

请保证你有连续的20分钟来看这个算法，如果你用2分钟就看明白了，好吧，你一定是超人。  
  
  
首先来描述下直接插入排序的算法，我们以升序为例。

数据准备：一个无序的整形数组： \{5, 8, 2, 7, 11, 20, 9, 1\}

算法介绍：

1. 当某个数组中只有一个元素的时候，我们认为此数组是有序的。

比如：\{5\}，他只有一个元素，那他就是有序的，ok？  
  
  
2. 从需要排序的数组的第二个元素开始，我们将对他进行插入排序；  
  
  
3. 在上面的数组中第二个元素是 8 对吧？  
  
  
4. 真正的排序马上开始；

5. 我们拿到了 8， 同他前面所有的有序的子数组的每个元素进行比较，

对于我们的例子来讲，8 前面的“有序的子数组”就是 \{5\}，

那么 8 会跟 5 去比较。

比较的结果是 8 > 5，则不做任何处理；

8 接下来跟子数组的其他元素比较，我们发现已经比较完了，

那么ok，对 8 这个元素，因为他跟5相比，本身就是升序，所以我们没有做任何移动；

6. 到此，你会不会说我在说废话？没关系，好戏马上开始了。

8 的下一个元素是2。

2 也会跟他前面的“有序的子数组” 进行比较，此时这个子数组是 \{5， 8\}，

所以这次需要跟两个元素进行比较。

那么先跟谁比呢？答案是先跟 8 比较，具体过程如下：

1), 2 > 8 吗？不大于，好的，2 和 8 交换位置。

啊？不是吧？你不知道交换位置是怎么回事吗？那我先说下这个吧：

比如 你有两个瓶子，一个瓶子装着醋，一个瓶子装着酱油，现在你突然发神经，想要把这俩瓶子换换个。

怎么办呢？好办，你去找一个你喝过的雪碧的瓶子，你会这么做：

*  把醋倒到雪碧瓶子，那么醋瓶子就空了；
 *  把酱油倒到醋瓶子，那么酱油瓶子就空了，此时醋瓶子里面装了酱油哈；
 *  把雪碧瓶子的醋倒到酱油瓶子里，那么雪碧瓶子空了，此时酱油瓶子就装了醋了。

则交换后数组看起来是这样：

\{5, 2, 8, ...\} ，...代表剩下的未经排序的元素，因为暂时还不涉及他们，故省略；

2) 那么接下来，2 和 5 比较，2 > 5 吗？不大于，同理，2 和 5交换，交换后变成这样：

\{2, 5, 8, ...\}

3) 接下来还要比较吗？不用了，因为\{5, 8\}这两个元素已经比较完了。

好的，到此为止，我们看到的数组是这样的：

\{2, 5, 8, 7, 11, 20, 9, 1\}

7. 下面的问题就以此类推了，很简单，我们继续啰嗦下下一个元素： 7 的排序过程：

7的前面的“有序的子数组”是\{2, 5, 8\}，因此，他需要比较3次。

同理，从后往前做比较，先跟8比：

1) 7 > 8 吗？不大于，好的交换，则为\{2, 5, 7, 8\};

2) 7 > 5 吗？是的，大于，好的，到此，我们可以停下来了；

3) 呃？你是说break吗？是的，就是break，为什么可以break呢？因为我们知道待比较的子数组是有序的，

所以呢，5前面的数字一定比5小（当然也可能等于，本例中没有出现这个情况而已，不管怎么样，他一定是小于等于5的）

那么，我们可以百分百确定，7不会出现在5的前面，所以就不跟前面的数字进行比较了。  
  
  
8. 我相信，如果你按照上面的自己一步步读下来，一定可以把最初的数组排序成功。

算法讲完了，那么我们来了解下他的时间复杂度是多少呢？

时间复杂度，是O(n^2)；这个时间复杂度我说不太清了，大家还是百度或谷歌吧。

空间复杂度，就是O(1)吧，因为我们只用了一个临时空间。

说到最后还是要用代码来实现，这是我的Java实现：

static void insertSort(int[] array) {
        int tmp = 0;
        for (int i = 1; i < array.length; i++) {
          tmp = array[i];
                 
          for (int j = i - 1; j >= 0; j--) {
            if (array[j] > tmp) {
              array[j+1] = array[j];
              array[j] = tmp;
            }
            else {
              break;
            } // End of else
          } // End of for (j)
        } // End of for (i)
      } // End of insertSort(..)

能看懂吗？

简单描述下：

第三行的for循环从 1 开始，咦？为什么是 1 呢? 数组下标不是从 0 开始吗？

对，你说的是对的，数组下标是从 0 开始，但对于我们的算法来讲，

从 0 开始，0 号元素前面是没有任何 “有序的子数组” 的，故我们从 1 开始，

那么 1 号元素前面的“有序的子数组”就是 \{0号元素\}。  
  
  
接下来，我们在第四行，把 i 号元素的值保存到 tmp 了；

下面第6行又是一个循环，在这个循环中，我们从 i - 1 开始，比较 i - 1 元素的值与 tmp 之间的关系。

如果要比较的元素 大于 tmp 了，那么就把他们换换位置；

否则呢，就break。  
  
  
这里break的原因在上面已经讲到了。  
  
  
  
  
此讲结束，下一讲准备是来说说 直接插入排序的改进算法：希尔排序。  
  
  
不知道你看完并理解整个过程花了多长时间呢？20分钟够吗？如果不够，原因是什么，是我写的不够详细看不明白？还是我写的太多了，光读文字就花了半小时呢 嘿嘿。  
  
  
Anyway, hope this helps.