插入排序算法在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

插入排序算法没有提供完美的输出。实现是否正确，以及如何修复输出.

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)):

改进

更多的Pythonic将使用range的能力来生成一个下降范围：

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

当if条件不为真时，继续内循环是无用的，因为这样可以保证if条件在内循环的其余迭代中永远不会是真的。因此，增加一个休息：

        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)更改len(array)+1，即，

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。