啥是插入排序？

亦凉 2023-09-25 21:45 22阅读 0赞

## 一、概述 ##

排序是算法中的一部分。所以我们学习排序也是算法的入门，为了能让大家感受到排序是算法的一部分，我举个例子证明一下：比如麻将游戏，发完牌之后需要对手上的牌进行排序，大家想想，麻将排序如何排呢？它有什么特点呢？而且在摸牌打牌的过程中，我们要不断的排序，如何排序呢？选择什么排序算法最快呢？

以上这种情况我们就可以分析选择哪种排序算法更高效。比如下图已经有一副固定顺序的牌了：

![2e8637d781334e1c838eecd898c8814d.png][]

此时轮到我们摸牌，摸到的牌如下：

![537a16e7a9d449fca3691ac8bfb237e2.png][]

此时，要将这个“三同”放到上面的一副牌中，就存在如下规律：

1、正常“3同”应该放到“2同”和”4同“中间。

2、跟其他花色的牌没有关系，甚至跟”5同“也没有关系。只需要把”3同“放到”2同“和”4同“中间就行。至于”2同”和”4同”在哪里不要紧。

我们前面学习了选择排序，如果使用选择排序对上面这副牌进行排序是否合适呢？显然是不合适的，因为选择排序必须从“七万”开始比较，选择最小牌跟第一张牌交换位置，依次类推。但是此处麻将牌的“3同”跟”七万“没有关系，不需要影响”7万“。所以使用选择排序不合适，因为时间负责度很高；此处使用插入排序会更好，什么是插入排序呢？就是本节需要介绍的内容。

## 二、插入排序 ##

插入排序属于简单排序的一种，通常指的简单排序只是因为其算法思路比较容易理解，不代表其用途很简单。为了让大家掌握插入排序，我们先看看插入排序的原理。

## 2.1、插入排序的原理 ##

首先有一个待排序的数组如下：

![27dfd6845c6e48aea0007ada731c7361.png][]

以上数组中只有一个数字0的顺序需要排列，其他数字的顺序都是对的。这种数组使用插入排序的效率更高，下面介绍此数组使用插入排序的流程。

1、先比较1和2，如果2比1小则交换位置。否则不交换位置。此数组不需要交换位置。

![12fd43efcfef43629b9948eb36a3075d.png][]

2、再比较2和3，如果3比2小，则交换位置。但是实际3比2大所以不交换位置，保持不变。

![351b76110e254d7198920b64596ee8e7.png][]

3、同理，3和4比较也不需要交换位置，保持不变

![ae606fd622af4f0baf355f220a33e4c4.png][]

4、接来下，4和0比较，0小于4，所以交换位置

![7ea43cc5d1114c7db6510f6c731d418c.png][]

交换位置之后的数组如下：

![c1714c21126b42fbafa6e8f4056a6c3b.png][]

5、因为3的邻居发生变化，所以3和0再次比较，0比3小，交换位置，交换之后的数组如下：

![1c5def5bad1c4836bf3e6d0611726e28.png][]

6、依次类推，0分别和2交换位置之后的数组如下：

![d9a2828b1d0f4c09832ee3ffd0186100.png][]

0再和1交换位置的数组如下：

![02540883491f43429b55c7551db3b0ba.png][]

这样一个数组的顺序就对了，但是循环还没有完成，因为我们刚才仅仅循环到数字4这个位置，数字5还没有比较。

7、最后比较4和5，如果5比4小则交换位置，但是5比4大，所以位置不变。数组循环完毕，最终排序如下：

![293c6374fc6d448a8f75a08aca8b027a.png][]

上面就是插入排序的原理。

## 2.2、插入排序和选择排序的区别 ##

比如就上面这个例子而言，插入排序是将0从索引为4的位置移动到索引3、2、1、0，最终才算结束。而选择排序是找到最小的值0，直接跟1进行交换，0到1的位置，1到0的位置。大家可以翻看前面关于选择排序的介绍。

## 三、插入排序的代码实现 ##

以下是java代码的实现：

/\*\* \* 插入排序 \*/ public static void algorithm5()\{ //原始数组 int\[\] array=\{1,2,3,4,0,5\}; //数组的长度 int length=array.length; //对数组进行遍历 for (int i = 0; i < length; i++) \{ //第二个循环仅仅是将当前数据跟自己左边的数字进行比较，如果小于左边数字则交换位置，否则位置不变。 for (int j = i; j > 0 && array\[j\]<array\[j-1\]; j--) \{ int temp = 0; temp = array\[j-1\]; array\[j-1\]=array\[j\]; array\[j\]=temp; \} \} //将排好序的数组打印输出 for (int i = 0; i < length; i++) \{ System.out.print(array\[i\]+"，"); \} \}

以上是插入排序的java代码实现，代码中的第二个for循环是重点，第二个for循环是只比较当前数据左边的值，如果比左边的值小则交换位置，否则位置不变。

## 3.1 插入排序的时间复杂度 ##

插入排序的时间复杂度有两种：

1、当数组本身是有序的，比如\{1，2，3，4，5\}，则采用插入排序的时间复杂度是O(n)。原因：如果数组本身是有序，插入排序需要每两个挨着的数字进行比较一次，总共比较N-1次，所以时间复杂度是O(n)。

2、当数组是无序的，最坏的情况下需要比较(n^2)/2次，所以时间复杂度是O(n^2)。

## 四、总结 ##

根据插入排序的时间复杂度来看，插入排序适合如下类型的数组：

1、数组中的每一个元素距离其最终的位置都不远。比如\{1,0,2,3,4,5\}，这个数组中0最终位置应该是第一个位置，0此时的位置距离第一个位置不远。

2、一个有序的大数组中融入一个小数组。比如有序大数组\{1,2,3,4,5,6\}，融入一个小数组\{0,1\}。

3、数组中只有几个元素的位置不正确。

上述这三种情况的数组适合使用插入排序算法。打过麻将的同学想想，打麻将过程中不停地摸牌、打牌、整理牌的过程是不是就是一次插入排序呢！

排序是算法的基础，排序的用途很多。看完本节内容之后，大家不妨自己动手写个代码将无需的扑克牌进行排序，看更适合哪种排序算法。

[2e8637d781334e1c838eecd898c8814d.png]: https://img-blog.csdnimg.cn/2e8637d781334e1c838eecd898c8814d.png
[537a16e7a9d449fca3691ac8bfb237e2.png]: https://img-blog.csdnimg.cn/537a16e7a9d449fca3691ac8bfb237e2.png
[27dfd6845c6e48aea0007ada731c7361.png]: https://img-blog.csdnimg.cn/27dfd6845c6e48aea0007ada731c7361.png
[12fd43efcfef43629b9948eb36a3075d.png]: https://img-blog.csdnimg.cn/12fd43efcfef43629b9948eb36a3075d.png
[351b76110e254d7198920b64596ee8e7.png]: https://img-blog.csdnimg.cn/351b76110e254d7198920b64596ee8e7.png
[ae606fd622af4f0baf355f220a33e4c4.png]: https://img-blog.csdnimg.cn/ae606fd622af4f0baf355f220a33e4c4.png
[7ea43cc5d1114c7db6510f6c731d418c.png]: https://img-blog.csdnimg.cn/7ea43cc5d1114c7db6510f6c731d418c.png
[c1714c21126b42fbafa6e8f4056a6c3b.png]: https://img-blog.csdnimg.cn/c1714c21126b42fbafa6e8f4056a6c3b.png
[1c5def5bad1c4836bf3e6d0611726e28.png]: https://img-blog.csdnimg.cn/1c5def5bad1c4836bf3e6d0611726e28.png
[d9a2828b1d0f4c09832ee3ffd0186100.png]: https://img-blog.csdnimg.cn/d9a2828b1d0f4c09832ee3ffd0186100.png
[02540883491f43429b55c7551db3b0ba.png]: https://img-blog.csdnimg.cn/02540883491f43429b55c7551db3b0ba.png
[293c6374fc6d448a8f75a08aca8b027a.png]: https://img-blog.csdnimg.cn/293c6374fc6d448a8f75a08aca8b027a.png