插入排序上的计数比较

Question

我很难弄清楚如何为我的插入排序创建一个计数器，在这个计数器中，它计算插入排序进行的比较次数。

简而言之，我想知道如何计算所有的比较，即使是while循环和for循环中的比较。

import random

class sorting:

    alist = []
    # 10 random numbers between 10 and 70
    for i in range(10):
        # integer random numbers between 10 and 70
        n = random.randint(10, 70)
        alist.append(n)
    print(alist)

    def insertionSort(alist,):
        for index in range(1, len(alist)):

            currentvalue = alist[index]
            position = index

            while position > 0 and alist[position - 1] > currentvalue:
                alist[position] = alist[position - 1]
                position = position - 1

            alist[position] = currentvalue

    insertionSort(alist)

Answer 1

这是正确的吗？

import random

类排序：

alist = []
# 10 random numbers between 10 and 70
for i in range(2):
    # integer random numbers between 10 and 70
    n = random.randint(10, 70)
    alist.append(n)
print(alist)



def insertionSort(alist):
    count = 0
    for index in range(1, len(alist)):

        currentvalue = alist[index]

        position = index

        while position > 0 and alist[position - 1] > currentvalue:
            alist[position] = alist[position - 1]
            position = position - 1
            count +=1


        alist[position] = currentvalue
    count += 1
    print(count)


insertionSort(alist)

Answer 2

您可以添加一个计数器，并按照注释中的建议保持其计数。最终代码如下所示

import random

class sorting:

alist = []
# 10 random numbers between 10 and 70
for i in range(10):
    # integer random numbers between 10 and 70
    n = random.randint(10, 70)
    alist.append(n)
print(alist)

def insertionSort(alist,):
    counter=0
    for index in range(1, len(alist)):

        currentvalue = alist[index]
        position = index
        counter +=2  # For the case postion <0 ........
        while position > 0 and alist[position - 1] > currentvalue:
            counter +=2
            alist[position] = alist[position - 1]
            position = position - 1

        alist[position] = currentvalue
    print(counter)
insertionSort(alist)