Article
分桶排序详解及实例实现/简单分桶
00 分钟
2020-3-9
2023-5-21
type
status
category
date
slug
summary
tags
icon
Last edited time
May 21, 2023 07:57 AM

一、什么是桶排序

桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。
对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要

二、实现方式

  1. 设置一个定量的数组当作空桶子。
  1. 寻访序列,并且把项目一个一个放到对应的桶子去。
  1. 对每个不是空的桶子进行排序。
  1. 从不是空的桶子里把项目再放回原来的序列中。

三、实现实例

伪代码:
元素分布在桶中:
notion image
元素分布在桶中:
notion image

四、关于桶排序的性能参数

1、时间复杂度

最坏时间复杂度: 平均时间复杂度: 最好时间复杂度:

2、空间复杂度

最坏空间复杂度:

3、是否稳定

稳定

4、适用于何类型存储

顺序存储和链式存储

五、代码实现

分桶原则使用简单分桶 关于归约化分桶有空再写..

算法部分

实例部分


评论