插入排序算法的python实现

Question

我试图在python中实现插入排序算法，并能够将其编码如下，我没有对整个数组进行排序，并且想知道这种实现是否具有适当的思想过程，如果不是，我会非常感激如果有人可以帮助我理解它，因为函数正在考虑从未排序的部分插入元素时数组的排序部分。此外，在您的审查中，请考虑执行是否正确，如果是，什么可以使我的解决方案输出正确。

def insertion_sort(array):
for i in range(1, len(array)):
for j in reversed(range(1, i)):
if array[j-1] > array[j]:
temp = array[j-1]
array[j-1] = array[j]
array[j] = temp
return array
to_sort = [4, 3, 1, 5, 6, 2]
print(insertion_sort(to_sort))

这是我得到的输出:[1,3,4,5,6,2]

tl;博士:插入排序算法没有给出完美的输出。实现是否正确?如何修复输出?

Answer 1

的目标函数是转变array[i]分类分区,但它确实array[i-1],因为内循环始于j等于i-1。

所以简单的修改是:

for j in reversed(range(1, i)):

:

for j in reversed(range(1, i + 1)):

改进更python化的方法是使用range的功能来生成降序范围:

for j in range(i, 0, -1):

当if条件不为真时，继续内循环是无用的，因为这样可以保证if条件在内部循环的其余迭代中永远不会为真。所以添加一个break:

if array[j-1] <= array[j]:
break
temp = array[j-1]
array[j-1] = array[j]
array[j] = temp

由于这些交换将总是将相同的值向左移动，即array[j]将始终是最初在array[i]的值，因此首先找到array[i]应该移动到的索引，然后执行一次旋转将其移到那里的成本更低。

def insertion_sort(array):
for i in range(1, len(array)):
temp = array[i]
for k in range(i - 1, -1, -1):
if array[k] <= temp:
break
else:
k = -1
# rotate
array[k+2:i+1] = array[k+1:i]
array[k+1] = temp
return array

我在这里使用了k，以免与原始代码中j的含义混淆:k是j - 1。

k(或j)的搜索可以通过调用next来完成:

def insertion_sort(array):
for i in range(1, len(array)):
temp = array[i]
j = 1 + next((k for k in range(i - 1, -1, -1) if array[k] <= temp), -1)
array[j+1:i+1] = array[j:i]
array[j] = temp
return array

Answer 2

您永远不会触及数组的最后一个元素，我建议用len(array)+1更改len(array)，即

def insertion_sort(array):
for i in range(1, len(array)+1):
for j in reversed(range(1, i)):
if array[j-1] > array[j]:
temp = array[j-1]
array[j-1] = array[j]
array[j] = temp
return array

这是因为i的最大值为len(array)-1,j的最大值为i-1，即len(array)-2。但是，数组中最后一个元素的索引是len(array)-1。