时间戳

首页 > 解决方案 > 二进制插入排序与快速排序

python - 二进制插入排序与快速排序

问题描述

我正在研究不同的排序算法及其性能（链接），然后我尝试自己实现一些排序算法。我也想改进它们，所以当我编写插入排序时，我想为什么不使用二进制搜索，因为数组的第一部分已经排序，为了摆脱交换，使用额外的数组. 代码可以在我的 GitHub或这里找到：

def insertion_sort_optimized(arr):
    array = [arr[0]]
    for i in range(1, len(arr)):
        index = bisect_left(array, i)
        array.insert(index, i)
    return array

然后我像往常一样实施了快速排序（链接）：

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    smaller_part = []
    larger_part = []
    pivot = arr[len(arr) - 1]
    for i in range(len(arr) - 1):
        if arr[i] < pivot:
            smaller_part.append(arr[i])
        else:
            larger_part.append(arr[i])
    return quicksort(smaller_part) + [pivot] + quicksort(larger_part)

然后我生成了一个包含 1.000.000 个数字的随机数组，并使用这个辅助函数比较了它们的性能：

def test_sorting_algorithm(sort=None, version="normal", returns=False, n=1000000):
    if version.lower() == "normal":
        print("Normal version:")
    else:
        print("Optimized version:")
    arr = [int(random() * n) for _ in range(n)]
    print(arr)

    start = time.time()
    if returns:
        arr = sort(arr)
    else:
        sort(arr)
    end = time.time()

    print(arr)
    print(f"Time elapsed: {end - start}\n")

所以它基本上运行给定的sort函数并打印对数组进行排序所花费的时间。所以我运行这段代码至少 10 次，每次二进制插入排序几乎快 9 倍（9s > 1s）。但我认为快速排序是最快的......如果我比较这两种排序算法，我会说二进制插入排序更好，尽管它需要 O(n) 额外的空间（最差的时间复杂度是 O(n* log(n)) 比快速排序更好...)。这是一个错误吗？快速排序实际上比二进制插入排序更差吗？我试图在整个互联网上找到它，但找不到与我的代码真正相似的东西。也许它甚至不是二进制插入排序，而是其他东西......（另一个名字）？

标签： pythonarraysalgorithmperformancesorting

解决方案

让我们看看您编写插入排序的尝试：

def insertion_sort_optimized(arr):
    array = [arr[0]]
    for i in range(1, len(arr)):
        index = bisect_left(array, i)
        array.insert(index, i)
    return array

您不是在插入数组值，而是在插入索引。以递增的顺序。所以这是错误的，它是 O(n log n)，而不是正确版本所需的 O(n^2)（由于每个 的线性时间insert）。

推荐阅读