Python3：插入排序比较计数器

Question

我需要为我的插入排序程序添加一个总比较计数器，但我不知道为什么我的比较总数为 0！

我知道比较输出应该是 15（对于我的特定数组）而不是 0。

到目前为止，这是我的代码：

def insertionSort(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k
        while values[i] > values[i+1]:
            temp = values[i]
            values[i] = values[i+1]
            values[i+1] = temp
            comparisons += 1 #I think this is wrong
        k = k + 1
    return comparisons, values

我做错了什么？

Answer 1

希望这有效

def insertion(a,length):
    count=0
    for i in range(1,length):
        key=a[i]
        jj=i
        while(jj>0 and a[jj-1]>key):
            a[jj]=a[jj-1]
            jj=jj-1
            count += 1
        a[jj]=key
    print count

没有。交换的数量将等于您使用 while 循环移动元素的元素数。因此，您可以在 while 循环中使用一个标志变量，以检查循环是否针对每个元素运行，并在每次标志变量显示交换时将计数器变量增加 1。

Answer 2

我刚刚检查了您的代码，它没有用于排序 [7,5,4,6]。

这是修改后的版本 -

def insertionSort_mod(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k+1
        curr_val = values[i]
        comparisons += 1
        while i>0 and values[i-1] > curr_val:
            values[i] = values[i-1]
            i=i-1
            comparisons += 1
        values[i] = curr_val
        k = k + 1
    return comparisons, values

print insertionSort_mod( [1, 2, 3, 55, 5, 6, 8, 7, 9, 111])

输出这个：

(15, [1, 2, 3, 5, 6, 7, 8, 9, 55, 111])

在您的上下文中，k+1 应该是当前索引，所以 i 应该是 k+1 并且应该与之前的值 i-1 进行比较

Python3：插入排序比较计数器

Python 3: Insertion Sort comparisons counter

python

algorithm

comparison

insertion-sort

python-3.x