python - 桶排序比快速排序更快

Question

我用 Python 编写了一个程序，它使用不同的算法对随机创建的包含 5000 个数字的列表进行排序并比较时间。
Quicksort 通常比 Bucket sort 慢，为什么？
我认为 Quicksort 更快。

这是我的程序:

快速排序

def quicksort(seq):
    wall = 0
    pivot = seq[-1]
    for index, num in enumerate(seq):
        if num < pivot:
            seq[wall], seq[index] = seq[index], seq[wall]
            wall += 1
    seq[wall], seq[-1] = seq[-1], seq[wall]
    left = seq[:wall]
    if len(left) > 0:
        left = quicksort(left)
    right = seq[(wall + 1):]
    if len(right) > 0:
        right = quicksort(right)
    return left + [pivot] + right

桶排序

def bucket_sort(seq):
    biggest = 0
    for number in seq:
        if number > biggest:
            biggest = number
    buckets = []
    buckets.append([]) * (biggest / 10 + 1)
    for number in seq:
        buckets[number / 10].append(number)
    for index, bucket in enumerate(buckets):
        #Using quicksort to sort individual buckets
        buckets[index] = quicksort(bucket)
    new_list = [number for number in bucket for bucket in buckets]
    return new_list

Answer 1

如您所知，当您需要对大量元素进行排序时，快速排序 是一个不错的选择。当您处理较小的集合时，桶排序 可能是更好的选择。

Quicksort 是分而治之算法的一个例子，它在排序之前完成它的主要工作 递归调用，划分其数据(使用分区)。在这种情况下，您的算法不是 pythonic，也不是真正的快速排序算法!

所以我建议使用这个算法而不是那个:

def quicksort(seq):
    if len(seq) <= 1: 
        return seq
    lo, pi, hi = partition(seq)
    return quicksort(lo) + [pi] + quicksort(hi)

def partition(seq):
    pi, seq = seq[0], seq[1:]
    lo = [x for x in seq if x <= pi]
    hi = [x for x in seq if x > pi]
    return lo, pi, hi