为什么插入排序和快速排序相结合会导致更糟糕的结果？

Question

我尝试设置一个截止点来组合快速排序和插入排序，当n(要排序的数据数)低于截止值时使用insert排序。然而，我发现这个方法不起作用，甚至比以前更糟糕。为什么以及如何改进它？

要对10e4随机整数进行排序，具有截止值(50)的快速排序需要0.6s，没有截止值的方法只需要0.02s。

具有截止点(50)的快速排序：

def quick_sort(line, l, r):
    if r - l > 50:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        insert_sort_index(line, l, r)


def find_median(line, l, r):
    center = (l + r) / 2
    if line[l] > line[r]:
        line[l], line[r] = line[r], line[l]
    if line[l] > line[center]:
        line[l], line[center] = line[center], line[l]
    if line[center] > line[r]:
        line[center], line[r] = line[r], line[center]
    line[center], line[r-1] = line[r-1], line[center]
    return line[r-1]


def insert_sort_index(line, l, r):
    if l < r:
        for idi in range(l+1, r+1):
            data = line[idi]
            for idj in range(idi+1)[::-1]:
                if idj >= l+1 and line[idj-1] > data:
                    line[idj] = line[idj-1]
                else:
                    break
            line[idj] = data

没有截止点的方法：

def quick_sort(line, l, r):
    if r - l > 1:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        if r == l + 1:
            if line[l] > line[r]:
                line[l], line[r] = line[r], line[l]

Answer 1

python3将range和其他函数作为迭代器/生成器来实现，因此在这个应用程序中它可能会更高效，但是python2 range函数在内存中创建了一个完整的列表。多次使用range (并使用::-1连接创建另一个列表)。您可以将步骤作为参数传递到该步骤的范围中)。

对于范围(0，x)的循环，我的python2实现似乎是在优化，这使得演示问题变得更加困难，但当(l，r)在更大的列表中时，就不是这样了，就像这个快速排序截止的情况一样。

我量了一下。当对较大列表的范围进行操作时，插入排序的速度加倍，方法是为idi、idj而不是range()使用while循环。