How to write bucket sort algorithm in Python?

How to write the bucket sort algorithm in Python?

Introduction:
Bucket Sort is a non-comparative sorting algorithm. Its principle is to divide the elements to be sorted into different buckets, and then sort the elements in each bucket. , and finally take out the elements in all buckets in order to get the sorted results. Bucket sorting is suitable for situations where the elements to be sorted are within a certain range and evenly distributed. The time complexity is O(n k), n represents the number of elements to be sorted, and k represents the number of buckets.

Specific steps:

1. Determine the minimum min_value and maximum max_value of the elements to be sorted;
2. Calculate the number of buckets bucket_num. The simplest way is to The range of sorted elements is equally divided according to the number of buckets to be divided;
3. Create bucket_num buckets, represented by lists, and each bucket is initialized to an empty list;
4. Put the elements to be sorted into the corresponding In the bucket, the specific method is to map the elements to the corresponding bucket according to the rules. In this example, we will divide the element by (max_value-min_value 1), round it, and then subtract the minimum value to obtain the subscript of the bucket;
5. To sort the elements in each non-empty bucket, you can use any sorting algorithm;
6. Dump all the buckets in order to get the sorted results.

Code implementation:

def bucket_sort(arr):
    min_value, max_value = min(arr), max(arr)
    bucket_num = len(arr)
    bucket_size = (max_value - min_value + 1) // bucket_num + 1  # 计算桶的大小，加1是为了包含最大值
    buckets = [[] for _ in range(bucket_num)]  # 创建桶

    # 将元素放入桶中
    for val in arr:
        index = (val - min_value) // bucket_size  # 计算桶的下标
        buckets[index].append(val)

    # 对每个桶中的元素进行排序
    for bucket in buckets:
        bucket.sort()

    # 将所有桶中的元素依次取出
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

Test:

arr = [4, 1, 9, 6, 3, 7, 5, 8, 2]
sorted_arr = bucket_sort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

Summary:
Bucket sorting is a simple and effective sorting algorithm, with a relatively even distribution of elements In the case of , linear time complexity can be achieved. However, the disadvantage of bucket sorting is that it takes up additional memory space, which may not be applicable when memory consumption is large. In practical applications, it is critical to choose an appropriate sorting algorithm based on the distribution of elements to be sorted.

The above is the detailed content of How to write bucket sort algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!