python - 比较合并和插入排序的问题

问题描述

我试图运行插入排序和合并排序并绘制它们。我花时间为 5 个不同的 N 绘制它们。我想这样做三遍，这样插入时间<合并时间，插入时间=合并时间和插入时间>合并时间。但是，无论我将 N 设置为多少，插入排序总是要快得多。这是我的输出 N = 5000

N 值：[1、1001、2001、3001、4001]

合并排序：[0.005, 11.198, 21.965, 35.996, 49.971000000000004]

插入排序：[0.002, 0.268, 0.545, 0.9129999999999999, 1.177]

我尝试了不同的 N 高达 10000000 并且合并排序总是较慢。我在这里想念什么？

def insertion_sort(array):
    start_time = datetime.datetime.now()
    for j in range(1, len(array)):
        key = array[j]
        i = j - 1
        while i >= 0 and array[i] > key:
            array[i + 1] = array[i]
            i -= 1
        array[i + 1] = key
    time_diff = datetime.datetime.now() - start_time
    return time_diff.total_seconds() * 1000

def merge_sort(arr, p, r):
    start_time = datetime.datetime.now()
    if p < r:
        m = (p + (r - 1)) // 2
        merge_sort(arr, p, m)
        merge_sort(arr, m + 1, r)
        merge(arr, p, m, r)

    time_diff = datetime.datetime.now() - start_time
    return time_diff.total_seconds() * 1000

def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = arr[p + i]

    for j in range(0, n2):
        R[j] = arr[q + 1 + j]

    i = 0
    j = 0
    k = p

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
    return arr

x, y1, y2 = [], [], []
N = 5000
for i in range(1, N, N // 5):
    array = [j for j in range(i)]
    array = array[::-1] # Array in reversed order
    x.append(i)
    y1.append(merge_sort(array, 0, len(array) - 1))
    y2.append(insertion_sort(array))

标签： pythonalgorithm

插入排序在已排序的数组上运行得非常快。它只是进行 n 次比较，仅此而已。

所以，给你一个问题：为什么在你的代码中使用排序数组调用插入排序？

提示：尝试改变这两行的顺序，看看运行时间如何变化：

    y1.append(merge_sort(array, 0, len(array) - 1))
    y2.append(insertion_sort(array))

python - 比较合并和插入排序的问题

问题描述

解决方案

推荐阅读