Python 中的插入排序算法
- 在 Python 中执行插入排序的步骤
- Python 中的插入排序算法
- Python 中插入排序的实现
- Python 中插入排序算法的复杂度
- Python 中插入排序的特点
- Python 中的二进制插入排序
插入排序算法的机制就像扑克牌。最初，我们拿第一张卡片并假设它已经排序。
因此，剩余的卡片是未排序的列表。然后，我们将一张一张地从这个未排序的列表中挑选卡片，并将它们与排序列表中的卡片进行比较。
这样，我们就可以为卡片找到合适的位置并相应地放置它。重复这个过程为我们提供了分类的卡片包。
插入排序也以这种方式工作。顾名思义，我们在插入元素的同时进行比较。
在 Python 中执行插入排序的步骤
让我们取一个包含这些元素的未排序数组：
15, 11, 17, 3, 5
我们采用已经按约定排序的第一个元素。
`15`, 11, 17, 3, 5
我们将从第二个元素到最后一个元素循环遍历 i = 1 到 i= 4。当 i =1 时，我们将 11 与它的前辈进行比较。由于 11 小于 15，我们移动 15 并在其前面插入 11。
`11`, `15`, 17, 3, 5
对于 i = 2，我们将 17 与其前身进行比较。这一次，因为 17 大于 11 和 15，所以它在 15 之后。
`11`, `15`, `17`, 3, 5
对于 i = 3，我们将 3 与其前任进行比较。3 现在将移至开头。
`3`, `11`, `15`, `17`, 5
对于 i = 4，我们将 5 与其前任进行比较。5 将放置在 3 之后和 11 之前。
`3`, `5`, `11`, `15`, `17`
这就是我们在 python 中使用插入排序获得排序数组的方式。
Python 中的插入排序算法
按照惯例，我们假设第一个元素已经在列表中排序。列表的其余部分被认为是未排序的。
之后，我们将通过保持列表中已排序部分的顺序，开始将未排序部分的元素插入到已排序部分。我们将使用以下步骤。
- 从未排序的列表中选择下一个元素并将其标记为
key。 - 选择
key并将其与排序列表中存在的所有元素进行比较。 - 如果
key元素大于排序数组中的元素，则移动到列表中的下一个元素。否则，将列表中较小的元素向左移动。 - 在排序列表中的正确位置插入
key，以保持排序列表中的顺序。 - 重复上述步骤，直到整个列表被排序。
Python 中插入排序的实现
下面是用 Python 语言实现插入排序的代码。
#Code in Python
#Function that performs Insertion sort
def Insertion_sort(arr):
#Loop till the last element starting from the second one
for i in range(1, len(arr)):
key_ele = arr[i]
#set the position of elements based on their value
t = i-1
while t >= 0 and key_ele < arr[t]:
arr[t + 1] = arr[t]
t -= 1
arr[t + 1] = key_ele
arr = [23, 45, 22, 6, 11]
Insertion_sort(arr)
for i in range(len(arr)):
print("% d" % arr[i])
输出：
6
11
22
23
45
我们首先定义一个函数 Insertion_sort()。我们在这个函数中应用排序逻辑。
我们从第二项遍历数组，并将键与已排序的元素进行比较。在每次迭代中，我们将列表中的元素值存储在另一个变量 key_ele 中。
然后，我们使用一个变量来存储最后一个元素的索引值。这样，我们可以使用 t 和 key_ele 的值来进行比较。
根据键元素的值，我们移动元素并将键放置在排序列表中。
在函数定义中，我们声明了一个数组。在 Python 中，我们称其为列表。
然后，我们调用 insertion_sort 函数。我们将列表作为参数传递给此函数。
该函数在排序后返回列表。最后，我们可以使用 for 循环来打印排序列表。
Python 中插入排序算法的复杂度
时间复杂度
最佳情况下的复杂度 - 数组已经排序。因此，不需要排序，最好情况下的复杂度是 O(n)。
平均情况下的复杂度 - 数组既不是升序也不是降序。它是随机混杂的。平均时间复杂度为 O(n^2)。
最坏情况下的复杂度 - 当数组已经按降序排序时，按升序排列，反转数组。最坏情况的时间复杂度是 O(n^2)。
空间复杂度
插入排序的空间复杂度是 O(1)，因为我们需要一个额外的变量来执行交换操作。
插入排序算法基于增量范式，是一种稳定算法。
Python 中插入排序的特点
- 该算法易于实现。
- 插入排序对于处理一小组元素是有效的。
- 我们甚至可以在已经排序的数据上使用它。它是一种自适应算法。
Python 中的二进制插入排序
二元插入排序是插入排序的临时版本，它有助于减少在正常插入排序中发生的比较次数。
这个想法很简单——我们使用二进制搜索来找到键的正确位置。这样，我们可以将第 i 次迭代的搜索复杂度从 O(i) 降低到 O(log i)。
然而，最坏情况的复杂度仍然是 O(n^2)。
综上所述，我们了解了插入排序及其在 Python 中的实现。
插入排序对于少量元素的排序是有效的，但是对于大集合我们应该使用其他算法，例如合并排序和快速排序。该算法的简单性使其脱颖而出。