【数据结构与算法】——插入排序

淡淡的烟草味﹌ 2022-08-09 06:23 141阅读 0赞

# 【定义】 #

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据

# 【分类】 #

插入排序分为两种：直接插入排序和希尔排序

##  直接插入排序 ##

###           基本思想：每次选择一个元素K插入到之前已排好序的部分A\[1…i\]中，插入过程中K依次由后向前与A\[1…i\]中的元素进行比较。若发现发现A\[x\]>=K,则将K插入到A\[x\]的后面，插入前需要移动元素。 ###

![Center][]

![Center 1][]

插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

### 时间复杂度 ###

最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)

最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n2)

平均情况下：O(n2)

### 空间复杂度  ###

在排序过程中仅需要一个元素的辅助空间，所以空间复杂度为为O(1)。

稳定性

直接插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以直接插入排序是稳定的。

因而，直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么直接插入排序还是一个不错的选择。

## 希尔排序 ##

![Center 2][]

### 基本思想:先将整个待排序记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，在对全体记录进行一次直接插入排序。 ###

### 具体做法：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，即将所有距离为d1倍数序号的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d2<d1），重复上述分组和排序工作，以此类推，直到所取的增量di=1，即所有的记录放在同一组进行直接插入排序为止。 ###

### 时间复杂度：O(n 1.3) ###

### 空间复杂度：在排序过程中仅需要一个元素的辅助空间用于数组元素值得交换，所以为O(1) ###

###     ###

### 稳定性： ###

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。对中等大小规模表现良好，对规模非常大的数据排序不是最优选择。并且希尔排序非常容易实现，算法代码短而简单。

[Center]: /images/20220731/4cc4928a142346408396e2416af990d9.png
[Center 1]: /images/20220731/3a5d25e88bb24df3af5c6ddb17ab4f20.png
[Center 2]: /images/20220731/1039cfc5678f4cc1b21f2dacdd5956d0.png