比较计数器插入排序-解网

问：

quick_sort_median(array[:], 0, n-1, 0)

我正在进行快速排序，并向其传递以下参数。当我的数组维度小于 3 时，我调用插入排序。在我看来，我错误地计算了比较。这是我的功能

def insertion_sort(array, p, r, count):
    for i in range(p+1, r+1):
        key = array[i]
        j = i - 1
        while j >= p and array[j] > key:
            if(array[j-1] > array[j]): count += 1
            j -= 1
        array[j-1], array[j] = array[j], array[j-1]
        array[j+1] = key
        count += 1
    return array, count

感谢您的帮助或批准。

我试着把计数器放在不同的地方

Python 算法比较排序

目前，您正在计算评估的次数，这是真的。当它是假的时，它不算数，但它应该算数。array[j-1] > array[j]
这种比较对算法没有贡献。array[j-1] > array[j]
这种比较可能引用一个小于的索引，该索引（当为 0 时）甚至可能触发错误。array[j-1] > array[j]pp
该算法执行的交换次数与（子）列表中的元素数量一样多。这是错误的。相反，插入排序应将值旋转到正确的位置。
该列表是就地排序的，因此它不必返回列表。
调用将复制列表，这会适得其反。快速排序和插入排序都应该进行就地排序，因此不需要复制列表。quick_sort_median(array[:], 0, n-1, 0)

以下是对数据比较进行适当计数的可能更正：insertion_sort

def insertion_sort(array, p, r, count):
    for i in range(p+1, r+1):
        key = array[i]
        # Walk backwards in the sorted partition
        for j in range(i, p, -1):
            count += 1
            if key >= array[j - 1]:
                break
            array[j] = array[j - 1]  # move value to the right
        else:
            j = p
        # place key in the sorted partition
        array[j] = key
    return count

的调用不应该做，而是按原样传递列表。insertion_sort[:]

上一个：在 Excel 中交叉比较两个不同的数据对以发现差异的有效方法是什么？

下一个：一种算法的预处理会改变实验条件吗？

比较计数器插入排序

Counter of comparisons insertion sort

评论