为什么我的python版本hoare分区快速排序比lomuto分区慢？

Question

通常，在实现快速排序时，Hoare的方案比Lomuto的分区方案效率更高，因为平均交换次数更少。为了验证这一点，我尝试在所有可能的重复元素排列中计算交换。我生成了一个8个元素的所有可能的可重复排列的列表来进行测试，总共是8的8次方。但在我的机器上的结果是奇怪的，霍尔的方案更慢，即使交换更少。以下是python代码：

import copy
import time

swap_lomuto = 0
swap_hoare = 0

def hoare_partition(a, p, r):
    global swap_hoare
    pivot = a[(p+r)//2]
    i = p - 1
    j = r + 1
    while True:
        i = i + 1
        j = j - 1
        while a[i] < pivot:
            i = i + 1
        while a[j] > pivot:
            j = j - 1
        if i < j:
            a[i], a[j] = a[j], a[i]
            swap_hoare += 1
        else:
            return j

def quick_sort_hoare(a, lo, hi):
    if lo < hi:
        p = hoare_partition(a, lo, hi)
        quick_sort_hoare(a, lo, p)
        quick_sort_hoare(a, p+1, hi)


def lomuto_partition(a, p, r):
    global swap_lomuto
    pivot = a[r]
    i = j = p
    while j < r:
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i = i + 1
            swap_lomuto += 1
        j = j + 1
    a[i], a[r] = a[r], a[i]
    swap_lomuto +=1
    return i

def quick_sort_lomuto(a, lo, hi):
    if lo < hi:
        p = lomuto_partition(a, lo, hi)
        quick_sort_lomuto(a, lo, p-1)
        quick_sort_lomuto(a, p+1, hi)

def gen_cases(n):
    a = list(range(1, n+1))
    r = [[]]
    def product(A, B):
        result = []
        for a in A:
            for b in B:
                result.append(a + [b])
        return result
    for i in range(n):
        r = product(r, a)
    return r

# generate 8**8 permutations with repeated elements
# e.g. [[1, 1], [1, 2], [2, 1], [2, 2]] when n == 2
n = 8
cases1 = gen_cases(n)
cases2 = copy.deepcopy(cases1)

start = time.time()
for c in cases1:
    quick_sort_lomuto(c, 0, len(c)-1)
end = time.time()
print("lomuto time: ", end-start)
print("lomuto swaps: ", swap_lomuto)

start = time.time()
for c in cases2:
    quick_sort_hoare(c, 0, len(c)-1)
end = time.time()
print("hoare time: ", end-start)
print("hoare swaps: ", swap_hoare)

# assert if two methods give the same result
for i in range(len(cases1)):
    for j in range(n):
        assert cases1[i][j] == cases2[i][j]

在我的机器上的结果是

洛穆托时间：46.35845708847046
洛穆托掉期：199594736
霍尔时间：59.410624027252
霍尔掉期：116165488

我想不出哪里错了

Answer 1

看看这个版本是否更好。这可能是一个解释器开销比算法效率影响更大的问题

如果对随机数或伪随机数进行排序，我发现Lomuto比Hoare稍微快一点

def qsort(a, lo, hi):
    if(lo >= hi):
        return
    p = a[(lo + hi) // 2]       # pivot, any a[] except a[hi]
    i = lo - 1
    j = hi + 1
    while(1):
        while(1):               # while(a[++i] < p)
            i += 1
            if(a[i] >= p):
                break
        while(1):               # while(a[ j] < p)
            j -= 1
            if(a[j] <= p):
                break
        if(i >= j):
            break
        a[i],a[j] = a[j],a[i]
    qsort(a, lo, j)
    qsort(a, j+1, hi)