Python 实现的插入排序
插入排序
插入排序（Insertion Sort）算法使用数组的一部分来存放已排序的值，另一部分来存放尚未排序的值。
{{ msgDone }}
该算法每次从数组未排序的部分中取出一个值，并将其放入已排序部分的正确位置，直到数组排序完成。
工作原理：
- 从数组未排序的部分中取出第一个值。
- 将该值移动到数组已排序部分的正确位置。
- 根据未排序部分中值的数量，再次遍历数组未排序部分。
手动运行示例
在 Python 程序中实现插入排序算法之前，让我们先手动对一个短数组进行排序，以了解其原理。
第 1 步：从未排序数组开始。
[ 7, 12, 9, 11, 3]
第 2 步：我们可以将第一个值视为数组已排序部分的初始值。如果只有一个值，那么它一定是已排序的，对吧？
[ 7, 12, 9, 11, 3]
第 3 步：现在，下一个值 12 应移动到数组已排序部分的正确位置。但是 12 大于 7，因此它已经在正确的位置。
[ 7, 12, 9, 11, 3]
第 4 步：考虑下一个值 9。
[ 7, 12, 9, 11, 3]
第 5 步：现在，值 9 必须移动到数组已排序部分的正确位置，因此我们将 9 移动到 7 和 12 之间。
[ 7, 9, 12, 11, 3]
第 6 步：下一个值是 11。
[ 7, 9, 12, > 11, 3]
第 7 步：我们将其移动到数组已排序部分的 9 和 12 之间。
[ 7, 9, 11, 12, 3]
第 8 步：最后一个要插入到正确位置的值是 3。
[ 7, 9, 11, 12, 3]
第 9 步：我们将 3 插入到所有其他值之前，因为它是最低值。
[ 3, 7, 9, 11, 12]
最终，数组已排序。
运行下面的模拟，以动画形式查看上述步骤：
在 Python 中实现插入排序
要在 Python 程序中实现插入排序算法，我们需要：
- 待排序的数组。
- 外部循环，用于选择一个要排序的值。对于包含 \(n\) 个值的数组，此外部循环跳过第一个值，并且必须运行 \(n-1\) 次。
- 内部循环，用于遍历数组的已排序部分，以找到插入值的位置。如果要排序的值位于索引 \(i\) 处，则数组的已排序部分从索引 \(0\) 开始，到索引 \(i-1\) 结束。
生成的代码如下所示：
实例
在 Python 列表上使用插入排序：
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1,n):
insert_index = i
current_value = mylist.pop(i)
for j in range(i-1, -1, -1):
if mylist[j] > current_value:
insert_index = j
mylist.insert(insert_index, current_value)
print(mylist)
插入排序的改进
插入排序还可以进一步改进。
上述代码首先移除一个值，然后将其插入到其他位置，这种方法很直观。例如，如果你用手中的一副牌进行插入排序，就会这样做。如果低值牌已排序到左侧，你会拿起一张新的未排序牌，并将其插入到其他已排序牌之间的正确位置。
以这种方式编程的问题在于，当从数组中移除一个值时，所有上方的元素都必须向下移动一个索引位置：
并且，当将移除的值再次插入到数组中时，还必须进行许多移动操作：所有后续元素都必须向上移动一个位置，以便为插入的值腾出空间：
这些移动操作可能会花费大量时间，尤其是对于包含许多元素的数组。
隐藏的内存移动：如果使用 Python 或 JavaScript 等高级编程语言，在代码中不会看到这些移动操作，但这些移动操作仍在后台进行。此类移动操作需要计算机花费额外时间来完成，这可能会成为问题。
你可以在此处了解有关数组在内存中存储方式的更多信息。
改进方案
我们可以通过仅移动必要的值来避免大多数这些移动操作：
在上面的图像中，首先复制值 7，然后将值 11 和 12 在数组中向上移动一个位置，最后将值 7 放在值 11 之前的位置。
在这种情况下，移动操作的数量从 12 减少到 2。
下面的示例实现了这一改进：
实例
在排序算法中插入改进：
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(1,n):
insert_index = i
current_value = mylist[i]
for j in range(i-1, -1, -1):
if mylist[j] > current_value:
mylist[j+1] = mylist[j]
insert_index = j
else:
break
mylist[insert_index] = current_value
print(mylist)
上述代码中还做了另一件事，即跳出内部循环。这是因为当我们已经为当前值找到正确的位置时，就没有必要继续比较值了。
插入排序的时间复杂度
插入排序对包含 \(n\) 个值的数组进行排序。
平均而言，每个值必须与其他大约 \(\frac{n}{2}\) 个值进行比较，以找到插入的正确位置。
插入排序必须运行循环来将值插入到其正确位置大约 \(n\) 次。
我们得到插入排序的时间复杂度：\( O( \frac{n}{2} \cdot n) = {O(n^2)} \)。
插入排序的时间复杂度可以如下所示：
对于插入排序，最佳、平均和最坏情况场景之间存在很大差异。
接下来是快速排序。最后，我们将看到一个更快的排序算法！