插入排序算法原理

发布时间：2023-06-28 14:17:14 所属栏目：教程来源：

导读：本节我们来聊一下基础排序中的插入排序算法。

1. 插入排序算法原理
插入排序的基本思想是：将整个数组 nums 分为有序和无序的两个部分。前者在左边，后者在右边。最开始有序的部分只有第一个元素，其余都属于无序

本节我们来聊一下基础排序中的插入排序算法。

1. 插入排序算法原理
插入排序的基本思想是：将整个数组 nums 分为有序和无序的两个部分。前者在左边，后者在右边。最开始有序的部分只有第一个元素，其余都属于无序的部分。每次取出无序部分的第一个(最左边)元素，把它加入有序部分。通过比较找到属于该元素的位置 k，然后将原 k 位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素，无序部分减少了一个元素。这样一直继续下去，直到无序的部分没有元素，整个插入排序就算完成。

2. 插入排序算法过程分析
简单点的话，可以从有序部分的最后开始往前依次比较。若有序元素比该插入值大则该有序元素后退一个位置，然后继续向前比较，直到有序列表中的元素小于该插入值。

3. 插入排序算法的优化
从上面的内容中可以很明显看出插入排序有一个可以优化的地方，就是插入排序中每次查找插入元素的位置时，我们可以利用前面已排好序的特点，使用二分法快速定位插入元素位置，这样会比从后向前一个一个比较要高效许多，特别是在排序规模较大时，尤为明显。

3.1 使用二分法的插入排序
二分法查找是一种非常高效的搜索方法，主要原理是每次搜索可以抛弃一半的值来缩小范围。其时间复杂度是O(log2n)，一般用于对普通搜索方法的优化。使用二分法时一定要保证数组是排序的，例如下面的数组：

5 8 10 12 17 20 25 26
假设想查找 10 的位置，首先给个头尾指针：first 和 end，分别指向 0 和 7 的位置。取中间数 mid = (0 + 7) / 2 = 3 ，而 nums[3] = 12 > 10，可知 10 的位置肯定在 first 和 mid 指针之间。此时我们将 end = mid，然后继续使用前面那样的方式在左边数组中查找，直到最后 first >= end 为止。

在 Python 中有一个二分查找模块：bisect，该模块中的方法都是基于二分查找法，可以使用 bisect_right() 方法来辅助我们快速实现插入元素的定位。首先在 Python 的交互式模式下测试下该方法：

>>> from bisect import bisect_right
>>> x = [, , , , , ]
>>> bisect_right(x, )
>>> bisect_right(x, )
>>> bisect_right(x, )
>>> bisect_right(x, )
可以看到，bisect_right() 方法快速返回了待插入元素在有序列表中的位置。

注意：在 bisect.py 模块中，bisect_right() 方法又给了一个别名，就是 bisect：

# 源码位置：lib/bisect.py
# ...
# Create aliases
bisect = bisect_right
于是我们给出基于二分法的插入排序算法：

from bisect import bisect
def insert_sort2(nums):
"""
插入排序: 使用二分法实现元素快速插入
"""
if not nums:
return False
for i in range(, len(nums)):
k = bisect(nums[:i], nums[i])
nums[k], nums[k + : i + ] = nums[i], nums[k:i]
return True
可以看到，使用了二分模块之后，插入排序算法的代码变得非常简洁，而且也相比原来的代码高效了不少。大家可以把排序的规模弄到万级别上进行测试和对比，就能够看到代码的区别。

3.2 基于链表的插入排序
对于使用的链表结构的数据我们无法向前面那样使用二分法进行插入位置的获取，但这样的链表结构有一个好处，就是我们找到对应的插入位置后，后面的元素不用整体后移，只需要 O(1) 的复杂度即可插入成功。

我们自定义一个有序链表的头部 head，这样是为了后面操作的方便。接下来每次从无序链表中选择一个数据插入到有序链表中，首先完成初始代码如下：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def insertion_sort_list(head):
# 定义一个新的有序节点
new_sorted = ListNode()
p = head
while p:
# 每次插入值为p.val的节点
# ...
# 重新指向下一个待插入的数据
p = p.next
return new_sorted.next
可以看到，比较核心的代码就是对于有序链表，如何插入一个值并保证链表的有序。我们的有序链表插入过程如下，需要准备 prev 和 cur 两个指针，分别表示当前比较的值的位置和上一个元素的位置。

本小节中，我们介绍了插入排序算法的排序原理及思路，同时分别完成了3种情况的插入排序算法，特别是最后一种情况的实现，涉及到链表操作，大家要多多练习，掌握这些基础的排序算法。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!