Python实现桶排序算法

2023-04-16 00:00:00 python 算法 排序

桶排序是一种基于计数的排序算法，它分为两个步骤： 1. 计数每个元素出现的次数； 2. 对原数组进行排序。

Python实现桶排序算法代码如下：

def bucket_sort(arr):
    # 确定桶的个数
    n = len(arr)
    bucket_num = 10
    bucket_range = (max(arr) - min(arr) + 1) // bucket_num
    buckets = [[] for _ in range(bucket_num)]
    # 将数组中的元素放入桶中
    for i in range(n):
        j = (arr[i] - min(arr)) // bucket_range
        buckets[j].append(arr[i])
    # 对每个桶中的元素排序，并放回原数组中
    index = 0
    for i in range(bucket_num):
        buckets[i].sort()
        for j in range(len(buckets[i])):
            arr[index] = buckets[i][j]
            index += 1
    return arr

在上述代码中，我们首先确定桶的个数（bucket_num），并计算每个桶所能容纳的范围（bucket_range）。之后，我们创建一个空的二维列表 buckets，将原数组中的每个元素按照区间范围放入不同的桶中。最后，我们对每个桶中的元素进行排序，并将排好序的元素放回原数组中即可。

下面我们来测试一下这个算法：

arr = [8, 4, 2, 9, 10, 7, 1, 3, 5, 6]
sorted_arr = bucket_sort(arr)
print(sorted_arr)

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

可以看到，该算法成功地对数组进行了从小到大的排序。

相关文章