python – Bucket排序比Quicksort更快

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – Bucket排序比Quicksort更快，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1445字，纯文字阅读大概需要3分钟。

内容图文

我在Python中创建了一个程序,该程序对包含5000个不同算法的数字的随机创建列表进行排序并比较时间.
Quicksort一般比Bucket排序慢,为什么？
我认为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

解决方法:

如您所知,当您需要对许多元素进行排序时,快速排序是一个不错的选择.当您使用较小的集合时,Bucket Sort可能是更好的选择.

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

内容总结

以上是互联网集市为您收集整理的python – Bucket排序比Quicksort更快全部内容，希望文章能够帮你解决python – Bucket排序比Quicksort更快所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端