Home > Article > Backend Development > 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:
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!