Algorithms - Bucket Sort - 桶排序

2021-01-19 03:14

阅读:549

标签:pre   name   ima   包含   nbsp   lin   htm   The   ref   

概念
    桶排序 Bucket Sort 假设待排序的输入数据服从均匀、独立地分布在区间 [ 0, 1 .
    桶排序将区间 [ 0, 1)划分为 n 个相同大小的子区间, 或称为 桶 bucket. 然后, 将输入的 n 个数据分别放到各个桶中. 
进而, 先对每个桶中的数进行排序, 然后遍历每个桶, 按照次序把各个桶中的元素列出来即可. 在桶排序的代码中, 假设输入是一个包含 n 个元素的数组 A, 且 每个元素 A[i] 满足: 0

算法需要一个临时数组 B[ 0, … ,n
-1 ] 来存放链表(即 B 为)

     技术图片
Python Programming

import insertion_sort           # 导入 inserttion sort 排序算法, 这里可以使用任何一种排序算法
# https://www.cnblogs.com/zzyzz/p/12910133.html
def bucket_sort(A): # 分治思想: 分组 -> 分别排序 -> 合并 n = len(A) B = [[] for x in range(n)] # prepare the bucket C = [] # 分组 for i in range(n): B [int(n*A[i])].append(A[i]) # insert A[i] to list B[n*A[i]] print(Factory:, B) # 经过分组的后的数组
# 排序 # 通过 insertion sort 算法, 对分组后的数组中的每一个元素分别排序 for j in range(n): insertion_sort.insertion_sort(B[j]) C.append(B[j]) print(Temp: , C)
# 合并
# processing and print the result # concatenate the list B[0],B[1], ... ,B[n-1] together in order res = [] for item in C: if item != ‘‘: for k in item: res.append(k) print(Result:,res) if __name__ == __main__: A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68 ] bucket_sort(A) 结果打印: Factory: [[], [0.17, 0.12], [0.26, 0.21, 0.23], [0.39], [], [], [0.68], [0.78, 0.72], [], [0.94]] # 经过分组的后的数组 # 通过 insertion sort 算法, 对分组后的数组中的每一个元素分别排序 Before: [] After: [] Before: [0.17, 0.12] Step 1 # insertion sort 排序的过程 111 0 1 0.17 0.12 222 0 1 0.17 0.12 333 -1 1 0.17 0.12 [0.12, 0.17] After: [0.12, 0.17] # 数组元素的排序结果 Before: [0.26, 0.21, 0.23] Step 1 111 0 1 0.26 0.21 222 0 1 0.26 0.21 333 -1 1 0.23 0.21 [0.21, 0.26, 0.23] Step 2 111 1 2 0.26 0.23 222 1 2 0.26 0.23 333 0 2 0.21 0.23 [0.21, 0.23, 0.26] After: [0.21, 0.23, 0.26] Before: [0.39] After: [0.39] Before: [] After: [] Before: [] After: [] Before: [0.68] After: [0.68] Before: [0.78, 0.72] Step 1 111 0 1 0.78 0.72 222 0 1 0.78 0.72 333 -1 1 0.78 0.72 [0.72, 0.78] After: [0.72, 0.78] Before: [] After: [] Before: [0.94] After: [0.94] Temp: [[], [0.12, 0.17], [0.21, 0.23, 0.26], [0.39], [], [], [0.68], [0.72, 0.78], [], [0.94]] # 待处理的排序的中间结果 Result: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94] # 排序的最终结果

 

Algorithms - Bucket Sort - 桶排序

标签:pre   name   ima   包含   nbsp   lin   htm   The   ref   

原文地址:https://www.cnblogs.com/zzyzz/p/12910761.html


评论


亲,登录后才可以留言!