python - 插入排序算法python有问题

Question

我正在做一个作业，给我们一个不超过 10^6 个数字的文本文档。可以是正的也可以是负的。然后我们的任务是创建一个函数，该函数使用插入排序算法将列表排序到定义的索引，该索引可能包含也可能不包含整个列表。然后我们需要它来输出排序列表和算法移动项目进行排序的次数(或者它必须迭代多少次才能对整个列表进行排序。

我让它与示例列表一起正常工作，只是对其进行排序，然后输出排序结果。我就是这样做的。

arr = [1,9,6,5,4,3,5,2]
n = 8

def insertionSort(arr, n):
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

insertionSort(arr, n)

print(arr)

这非常有效，我得到的输出是 [1,2,3,4,5,5,6,9]。但是，一旦我添加到我的柜台。它停止工作。我基本上只是在函数中添加了几行。

def insertionSort(arr, n):
    counter = 0
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter += 1
        arr[j+1] = key
    return arr, counter
    print(counter)

insertionSort(arr, n)

print(arr)

打印出来的和以前一样。因此，我根据错误移动了一些东西并结束了:

arr = [1,9,6,5,4,3,5,2] #[open("rosalind_ins.txt").read().split(' ')]
n = 8
counter = 0

def insertionSort(arr, n):
    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        #move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            counter += 1
        arr[j+1] = key
    return arr, counter

insertionSort(arr, n)
print(counter)
print(arr)

这给了我一个我不确定如何解决的错误，即 在赋值之前引用了局部变量“counter”。

所以我暂时放弃了，然后又遇到了另一个问题。 我只想至少让它工作，从 .txt 中提取数据并对其进行排序。因此，使用我收到的文件，我只是更改了程序的前两行，它给了我另一个错误，我不确定如何修复。

arr = [open("rosalind_ins.txt").read().split(' ')]
n = 811

此列表中有近 1000 个项目。 我在这里收到的错误是；

File "insertionSort.py", line 17, in insertionSort
    key = arr[i]
IndexError: list index out of range

我为文字墙道歉，可能问了一个简单的问题，但我已经坚持了 2 天，并且已经阅读了至少 4 篇关于插入排序的不同文章，但仍然一无所获。

Answer 1

您的第二个函数(您在第二个代码块中定义的函数)很好……但是您没有正确捕获返回参数。做

sorted_arr, counter = insertionSort(arr, n)

获取计数器。