桶排序比流沙快

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

好吧。首先，不要给已经有键名的变量命名，例如list。list已经为python内置，并将覆盖以前认为的list。

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

本例中的bucket值为[0,9]、[10-19]、[20-29]、[30-39]和[40-49]。 创建bucket之后，在每个bucket上使用排序算法，该算法可以是任何内容，包括bucket sort again。通常在bucket排序中，算法会查看最有效的位，并将其与另一个值的最有效位进行比较，如果它们匹配，则会一点一点地向下滚动，直到确定哪个更大。这种类型的排序也可以用于字符、列表等

最有效位（MSB）比较的快速示例： 3对9
二进制中的3是0011 二进制中的9是1001
在本例中，从最左边开始，我们看到0代表3，1代表9，因此9更大。
每一个桶分类后，您将得到以下结果：

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

Quicksort：
使用quicksort，首先要选择一个pivot元素。
之后，重新排序数组，使值小于轴心点的任何元素位于轴心点之前，而值大于轴心点的任何元素位于轴心点之后。
然后递归地对具有较小值的元素列表和具有较大值的列表执行此操作。这个概念是非常直截了当的，但是如果你不熟悉算法，选择一个好的轴心点也可能是一个挑战。

现在…为什么桶排序更快？
由于quicksort涉及到递归和轴心点，因此通常只限于O(n*log(n))

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

现在，如果您选择一个较慢的排序算法来对bucket sort中的bucket进行排序，那么quicksort可能会更快。

我知道这是一个非常高层次的概述，可能有点混乱，但希望这足以帮助您理解为什么bucket sort比quicksort快，但是quicksort比bucket sort快。

Answer 2

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

Quicksort是分治算法的一个例子，它在 递归调用，在分割其数据时（使用分区）。在这种情况下，你的算法不是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

Answer 3

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

由于此处给出的代码用于快速排序，因此它使用了两个新列表。i、 e.，低&高

The Speciality of QuickSort is not using new 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