桶排序比快速排序更快

Question

桶排序比快速排序更快

3

我已经用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

Bucket sort

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

- Matt

就此而言，list 是一个非常糟糕的名称，因为它隐藏了同名的内置类。 - David Heffernan

3

抱歉，我正在学习。 - Matt

通常快速排序被写成一个原地算法。修复这个问题可以将您的代码加速大约2倍。 - Paul Hankin

3个回答

2

好的。首先，尽量不要给已经有关键词的变量命名，比如list。list在Python中已经内置，并将覆盖以前被认为是list的内容。

桶排序：假设我们有一个列表[29, 25, 3, 49, 9, 37, 21, 43]。使用桶排序，它将把其中一些值分组到下面所示的桶中。

这种情况下的桶将值分组为[0,9]、[10-19]、[20-29]、[30-39]和[40-49]。创建桶后，然后对每个桶使用排序算法，这个算法可以是任何东西，包括再次使用桶排序。通常，在桶排序中，算法将查看最高有效位并将其与另一个值的最高有效位进行比较，如果它们匹配，则会逐位向下滴落，直到清楚哪个更大。这种类型的排序也可以适用于字符、列表等。

最高有效位（MSB）比较的快速示例： 3 vs. 9 3的二进制表示为0011， 9的二进制表示为1001。从最左边的位开始，在这种情况下，我们看到3的0和9的1，因此9更大。每个桶排序后，你将得到下面的结果。

桶排序的另一个例子可以在这里找到：桶排序快速排序：使用快速排序时，首先选择一个枢轴元素。然后重新排列数组，以便任何值小于枢轴的元素都位于枢轴之前，任何值大于枢轴的元素都位于枢轴之后。然后对具有较小值的元素列表和具有较大值的元素列表进行递归处理。这个概念非常简单，但如果你不熟悉算法，选择一个好的枢轴也可能是一项挑战。

那么...为什么桶排序更快呢？由于快速排序中涉及到递归和枢轴点，通常会受到O(n*log(n))的限制。

由于桶排序中桶的排序算法是MSB，因此该排序算法的时间复杂度为O(n+k)。

现在，如果你选择一个较慢的排序算法来对桶进行排序，那么快速排序可能会更快。

我知道这是一个非常高层次的概述，可能有点令人困惑，但希望它足以帮助你理解为什么桶排序比快速排序更快，以及如何让快速排序比桶排序更快。

- Chrispresso

这个答案完全没有帮助。 - Maciej Gol

OP 要么会从我这里了解桶排序为什么更快，要么会从其他地方了解。这个问题在互联网上和关于排序算法的很多教材中已经存在了很长时间，所以再次解释已经没有意义了。 - Chrispresso

在编写代码之前，我查看了这些链接以理解算法，我不明白为什么我的问题不好。无论如何，我重新查看了这些网站，但我仍然不理解。感谢帮助，抱歉我的英语。 - Matt

0

https://stackoverflow.com/posts/25690572/revisions

由于这里提供了快速排序的代码，它使用了两个新列表，即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

- Rakesh Kumar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mazdak · Accepted Answer

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

快速排序是分治算法的一个例子，在递归调用之前通过划分数据（使用分区）完成其主要工作。在这种情况下，您的算法不符合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