插入排序算法有问题 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)

这给了我一个错误，我不确定如何解决 local variable 'counter' is referenced before assignment.

所以我暂时放弃了，运行又遇到了另一个问题。我只想至少让它工作，从 .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

您的第二个函数（您在第二个代码块中定义的函数）很好……但是您没有正确捕捉到您的 return 参数。做

sorted_arr, counter = insertionSort(arr, n)

获得counter。

Answer 2

有一些问题。要解决索引错误，请将 n 设置为恰好是 arr 的长度。然后，为了修复计数器错误，将计数器移回本地范围（无论如何它的声明）。最后，您永远不会打开计数器和 arr 的包装，所以两者都得不到更新。

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

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

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

另请注意，我更改了 arr 的读入方式：

arr = open("rosalind_ins.txt").read().split(' ')

并取目标 n 和 len(arr) 的最小值，以避免索引超出数组末尾。

Answer 3

所以，我尝试了一些建议的解决方案并最终得到

arr = [open("rosalind_ins.txt").read().split(' ')]
n = len(arr)
counter = 0

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 = counter + 1
        arr[j+1] = key
    return arr, counter

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

它只是重新打印出输入的列表，以及0的计数器

Answer 4

好的只是想post解决这个问题。感谢 Dillon Davis，mortysporty。

arr = open("rosalind_ins.txt").read().split(' ')
n = 811
counter = 0

def insertionSort(arr, n):
    counter = 0
    arr = [int(i) for i in arr if isinstance(i, str)]
    # 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 = counter + 1
        arr[j+1] = key
    return arr, counter

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

插入排序算法有问题 python

Having an issue with an insertion sort algorithm python

python

algorithm

sorting

insertion-sort