桶排序比快速排序快

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

如您所知，当您必须对许多元素排序时，快速排序是一个很好的选择。当您使用较小的集合时，Bucket Sort可能是一个更好的选择。

Quicksort是分而治之算法的一个例子，它在递归调用之前完成其主要工作，对其数据进行分割(使用分区)。在这种情况下，您的算法不是节奏曲，也不是一个非常快速的排序算法！

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

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

Answer 2

好的。首先，不要给已经有键名的变量命名，例如，list。list已经为python内置，并将覆盖过去被认为是list的内容。

Bucket sort

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

​

​

本例中的桶值为[0,9]、[10-19]、[20-29]、[30-39]和[40-49]。一旦创建了桶，然后在每个桶上使用排序算法，这个算法可以是任何东西，包括桶排序。一般来说，在桶排序中，算法会查看最重要的位，并将其与另一个值中最重要的位进行比较，如果它们匹配，则会一点一点地滴下来，直到清楚哪一位更大。这种类型的排序也可以处理字符、列表等。

最重要位(MSB)比较的快速示例:3比9

3在二进制是0011 9在二进制是1001

从最左边的位开始，在这种情况下，我们看到0表示3，1表示9，因此9更大。

在对每个桶进行排序之后，您将得到以下结果：

​

Bucket sort的另一个例子可以在这里找到：桶分类

Quicksort

通过快速排序，您可以从选择一个枢轴元素开始。

在此之后，重新排序数组，以便值小于枢轴的任何元素都出现在枢轴之前，而值大于枢轴的任何元素则在枢轴之后。

然后递归地对具有较小值的元素列表和具有较大值的列表进行递归处理。这个概念非常直截了当，但是如果您不熟悉算法，那么选择一个好的支点也是一个挑战。

Now...why是桶排序更快吗？

由于快速排序涉及到递归和枢轴点，所以通常只限于O(n*log(n))

由于桶排序中桶的排序算法是最小均方排序算法，该排序算法的时间复杂度为O(n+k)。

现在，如果您选择了一种较慢的排序算法来对桶排序中的桶进行排序，则可以使快速排序更快。

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

Answer 3

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

由于这里给出了快速排序的代码，所以它使用了两个新列表。也就是说，洛&嗨

QuickSort的特点是不使用新的MemorySpace。

因此，回答的代码是一个很好的解决方案，但它确实打破了逻辑差异b/w快速和合并排序

(代码是修改后的版本，摘自下面的源代码)

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