桶排序算法实现详细分析

桶分类平均在线性时间运行。与计算排序一样, 存储桶排序也很快速, 因为它考虑了有关输入的某些内容。桶排序认为输入是通过随机过程生成的, 该过程在元素μ= [0, 1]上均匀分布元素。
要对n个输入数字进行排序, 请按存储桶排序

  1. 将μ划分为n个非重叠间隔, 称为存储桶。
  2. 将每个输入数字放入其存储桶中
  3. 使用简单的算法(例如, 插入排序, 然后
  4. 连接已排序的列表。
桶排序认为输入是n个元素数组A, 并且数组中的每个元素A [i]都满足0≤A[i] < 1。该代码取决于链接列表(存储桶)的辅助数组B [0 … . n-1], 并认为存在维护此类列表的机制。
BUCKET-SORT (A) 1. n ← length [A] 2. for i ← 1 to n 3. do insert A [i] into list B [n A[i]] 4. for i ← 0 to n-1 5. do sort list B [i] with insertion sort. 6. Concatenate the lists B [0], B [1] ...B [n-1] together in order.

示例:说明阵列上BUCKET-SORT的操作。
A = (0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 068)

解:
桶排序算法实现详细分析

文章图片
图:存储桶排序:第1步, 将密钥按排序顺序放入垃圾箱
桶排序算法实现详细分析

文章图片
图:存储桶排序:步骤2, 连接列表
桶排序算法实现详细分析

文章图片
【桶排序算法实现详细分析】无花果:桶排序:最后的排序顺序

    推荐阅读