桶排序比快排更快

Question

我写了一个用Python做的程序，这个程序会对一个随机生成的包含5000个数字的列表进行排序，并比较不同算法的耗时。
快速排序通常比桶排序慢，为什么呢？
我原以为快速排序会更快。

这是我的程序：

快速排序

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

在这里给出的代码是关于快速排序的，它使用了两个新的列表，也就是 lo 和 hi。

快速排序的特点是不使用新的内存空间

所以这个回答中的代码是一个不错的解决方案，但它打破了快速排序和归并排序之间的逻辑区别。

（这段代码是经过修改的版本，来源于下面提供的链接）

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
    if first<last:
        splitpoint = partition(alist,first,last)
        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
    pivotvalue = alist[first]
    leftmark,rightmark = first+1,last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        else:
            alist[first],alist[rightmark] = alist[rightmark],alist[first]

    alist[first],alist[rightmark] = alist[rightmark],alist[first]
    return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

来源: https://runestone.academy/runestone/static/pythonds/SortSearch/TheQuickSort.html

Answer 2

好的，首先要注意，不要给变量起与已有关键字相同的名字，比如说“list”。list在Python中是一个内置的关键字，如果你用它来命名变量，就会覆盖掉原来的list。

桶排序:
假设我们有一个列表 [29, 25, 3, 49, 9, 37, 21, 43]。使用桶排序时，会把这些值分到不同的桶里，如下所示。

在这个例子中，桶将值分为 [0,9]、[10-19]、[20-29]、[30-39] 和 [40-49]。一旦桶创建完成，就会对每个桶使用排序算法，这个算法可以是任何一种，包括再次使用桶排序。一般来说，在桶排序中，算法会查看最重要的位（MSB），并将其与另一个值的最重要的位进行比较，如果相同，就会逐位比较，直到确定哪个更大。这种排序方法也可以用于字符、列表等。

最重要的位（MSB）比较的简单例子：
3 和 9
3 的二进制是 0011
9 的二进制是 1001
从最左边的位开始，我们看到3是0而9是1，因此9更大。
每个桶排序后，你会得到这样的结果：

另一个关于桶排序的例子可以在这里找到： 桶排序

快速排序:
快速排序的开始是选择一个基准元素。
然后你会重新排列数组，使得任何小于基准的元素都在基准前面，而大于基准的元素都在基准后面。
这个过程会递归地应用到小于基准的元素列表和大于基准的元素列表上。这个概念比较简单，但如果你对算法不熟悉，选择一个好的基准可能会有点挑战。

那么...为什么桶排序更快呢？
因为快速排序涉及递归和基准点，通常时间复杂度是 O(n*log(n))。

而桶排序中桶的排序算法是基于最重要的位（MSB），所以它的时间复杂度是 O(n+k)。

如果你选择一个较慢的排序算法来排序桶，快速排序可能会更快。

我知道这只是一个很高层次的概述，可能有点让人困惑，但希望能帮助你理解为什么桶排序比快速排序快，同时也能理解在某些情况下快速排序可能会比桶排序快。

Answer 3

大家都知道，快速排序在需要排序很多元素的时候是个不错的选择。不过，如果你处理的是比较小的数据集合，桶排序可能会更合适。

快速排序是一种“分而治之”的算法，它在进行递归调用之前就完成了主要的工作，主要是通过划分数据来实现的（也就是用分区）。如果你的算法没有做到这一点，那就不算是真正的快速排序，也不够“Python风格”！

所以我建议你用这个算法来替代那个：

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