Python 桶排序

最后修改于 2025年3月8日

在本文中，我们将讲解 Python 中的桶排序算法。我们将介绍如何按升序和降序对数值和文本数据进行排序。最后，我们将比较桶排序和快速排序，并测试它们的性能。

算法 是解决问题或执行计算的分步过程。算法是计算机科学和编程的基础。

排序 是以特定顺序（例如升序或降序）排列数据的过程。排序对于高效的数据检索和分析至关重要。

常用排序算法

一些常见的排序算法包括

• 气泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 桶排序

桶排序算法

桶排序是一种基于分配的排序算法。它的工作原理是将元素分配到多个桶中，然后单独对每个桶进行排序。当输入均匀分布时，桶排序是有效的。

桶排序示例：数值数据

以下示例演示了按升序对数值数据进行桶排序。

def bucket_sort(arr):
    max_val = max(arr)
    size = max_val / len(arr)
    buckets = [[] for _ in range(len(arr))]

    for i in range(len(arr)):
        j = int(arr[i] / size)
        if j != len(arr):
            buckets[j].append(arr[i])
        else:
            buckets[len(arr) - 1].append(arr[i])

    for i in range(len(arr)):
        buckets[i] = sorted(buckets[i])

    result = []
    for i in range(len(arr)):
        result.extend(buckets[i])

    return result

arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
sorted_arr = bucket_sort(arr)
print("Sorted array:", sorted_arr)

此代码使用桶排序算法对浮点数列表进行排序。

桶排序示例：文本数据

以下示例演示了按降序对文本数据进行桶排序。

def bucket_sort_textual(arr):
    max_len = max(len(s) for s in arr)
    buckets = [[] for _ in range(max_len + 1)]

    for s in arr:
        buckets[len(s)].append(s)

    for i in range(len(buckets)):
        buckets[i] = sorted(buckets[i], reverse=True)

    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])

    return result

arr = ["apple", "banana", "kiwi", "mango", "pear"]
sorted_arr = bucket_sort_textual(arr)
print("Sorted array:", sorted_arr)

此代码按字符串的长度降序对字符串列表进行排序。

桶排序与快速排序的比较

桶排序和快速排序都是高效的排序算法，但它们有不同的用例。桶排序非常适合均匀分布的数据，而快速排序是一种通用的算法。

基准测试示例

以下示例比较了桶排序和快速排序的性能。

import time
import random

def bucket_sort(arr):
    max_val = max(arr)
    size = max_val / len(arr)
    buckets = [[] for _ in range(len(arr))]

    for i in range(len(arr)):
        j = int(arr[i] / size)
        if j != len(arr):
            buckets[j].append(arr[i])
        else:
            buckets[len(arr) - 1].append(arr[i])

    for i in range(len(arr)):
        buckets[i] = sorted(buckets[i])

    result = []
    for i in range(len(arr)):
        result.extend(buckets[i])

    return result

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [random.randint(0, 1000) for _ in range(10000)]

start_time = time.time()
bucket_sort(arr)
print("Bucket Sort Time:", time.time() - start_time)

start_time = time.time()
quick_sort(arr)
print("Quick Sort Time:", time.time() - start_time)

此代码对大型随机数据集测试桶排序和快速排序的性能。

来源

维基百科上的桶排序

在本文中，我们探讨了 Python 中的桶排序算法，并将其与快速排序进行了比较。桶排序对于均匀分布的数据是有效的，而快速排序是一种通用的多功能算法。

作者

我叫 Jan Bodnar，是一名充满激情的程序员，拥有丰富的编程经验。我从 2007 年开始撰写编程文章。到目前为止，我已经撰写了 1,400 多篇文章和 8 本电子书。我拥有超过十年的编程教学经验。

列出所有 Python 教程。