桶排序

简介:

一,介绍

①什么是桶排序?

桶排序是在已经数据的范围的条件下,创建若干个桶,根据相应的比较规则将待排数据落入各个对应的桶中,最后扫描 桶 来实现排序。

②桶排序需要的附加条件

数据的范围已知。

比如,输入整数数据 A(1)  A(2)......A(n-1)  A(n),它们都是由小于M的整数组成,此时,就可以创建 M 个桶进行桶排序了

再比如,固定长度的字母字符串数据: S(1) S(2) .....S(n-1) S(n),任意的字符串S(i),都由26个小写字母组成,在桶排序过程中,就可以创建26个桶来保存这些字符串

 

二,桶排序的示例

①将10万个人的年龄进行桶排序

假设有10万个人的年龄数据,年龄范围默认是0-99,如何对这10万个数据进行排序?

如果用快排啊、归并排序啊...这样的排序算法是可以。但是这样的排序问题更适合桶排序。采用桶排序的方法如下:

建立100个桶,这可以用一个 一维数组来表示。a[0...99],依次扫描10万条数据,根据每条数据的值,记录到桶中。比如,第10个人的年龄是18岁,则a[18]++ (这是将出现的频率记录在桶中,是计数,它是将待排序的元素本身进行比较,而不是将“待排序的元素的组成部分”进行比较)

然后,扫描这100个桶,即可得到有序的数组。

如:一个简单的示例:    所有的数据都在0-5范围内:

4,5,2,3,1,4,3,2,1,5,2,2,4,5,1,3,4,1,3,2,2

排序后.....

1,1,1,1,2,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5

 

②将20个范围为0-999的整数进行排序

如果按照①中的思路,则需要创建999个桶,然后进行一趟桶排序即可。

但是还有另外一种方式,只创建10个桶,但是要进行3趟桶排序。

10个桶对应0-9 一共10个不同的数字,说白了就是一个长度为10的整型数组。3趟桶排序是因为:0-999范围内的数由3个位组成:个位、十位、百位

第一趟对个位数进行桶排序,根据个位数的值,将该数放入对应的桶中,比如425,个位数为5,则将425放到a[5]中---(这是将元素本身放到桶中,不是计数,这种方式待排序的元素个数不能超过桶的个数!!!)

第二趟对十位数进行桶排序,根据十位数.....

第三趟对百位数进行桶排序,根据百位数.....

具体的实现可以这样:

在第一趟桶排序时,将待排的20个数依次放到桶中。然后,再把这20个数拷贝回原数组,然后再根据 十位 数排序:根据十位数的大小 将这20个数 按顺序放到桶中,然后再把十位数有序的桶中的数据复制回原数组......百位数....

最终,原数组中的数据就是 已经排好序的数据了。

(注意:可能一个桶里面存储了多个 数,比如: 425, 685 在第一趟桶排序时会被放入到同一个桶中

 

③将100个长度固定(比如5)的字符串进行排序

有100个字符串,每个字符串的长度为5,字符串只由小写字母表中的字母组成。

小写字母表共有26个,故需要26个桶。每个字符串的长度为5,需要进行5趟桶排序。

第一趟桶排序对所有字符串中最后一个字符进行比较,并将该字符串放到相应的桶中(是将元素本身放到桶中

然后,再把桶中的数据拷贝回原数组,以便进行第二趟比较。(因为,在下一趟桶排序中又需要将字符串根据下一个比较字符复制到桶中)

第二趟桶排序对所有字符串中的倒数第二个字符比较,并将该字符串放到相应的桶中

....

....

可以看出,这种类型的桶排序,并不是比较元素本身记录出现的次数,而是比较元素的组成部分并将元素本身放到桶中。因此,需要根据实际问题,采用何种记录方式。

比如,字符串 "china" ,所谓比较元素的组成部分是指,依次比较 "china" 中的各个字符 'a' 'n' 'i' 'h' 'c'。然后将字符串 "china" 存储到桶中。

 

三,上面字符串桶排序的实现分析

final int BUCKETS = 26;
ArrayList<ArrayList<String>> buckets = new ArrayList<>();

定义桶的大小,并用一个buckets来保存所有的桶

 

for(int i = 0; i < BUCKETS; i++)
    buckets.add(new ArrayList<String>());

桶的初始化,每个桶都可以保存若干个字符串(比如,在第一趟排序中,若 “bcrd” 和 “cmed” 的最后一个字符相同,故它们会被放到同一个bucket中)

 

复制代码
        for (int pos = stringLen - 1; pos >= 0; pos--)// 一共进行stringLen趟排序
        {
            for (String s : arr)
                buckets.get(s.charAt(pos) - 'a').add(s);// 根据比较的字符将 字符串放到相应的桶中

            int idx = 0;
            for (ArrayList<String> listStr : buckets){ 
                for (String str : listStr) 
                        arr[idx++] = str;//将桶中的数据放回到原数组中
                listStr.clear();//清空桶中的数据,以便下一趟排序做准备
            }
        }
复制代码

桶排序的核心代码,第一个for循环的次数是 字符串的长度,它表示的是进行多少趟桶排序

第二个for循环实现的功能是:对于待排序的每个字符串,根据该字符串的第 pos 位置的字符,来决定将该字符串放到哪个桶中去

第三个for循环则是:把桶中的每个字符串,依次按顺序取出,放回到原数组中。这里的按顺序表明:此时,字符串是按照 charAt(pos)这个字符串有序的。

比如,"bcao", "bcrd", "cmed", "glpq" 这四个字符串,在第一趟桶排序后,顺序是:"bcrd","cmed","bcao","glpq"。即,根据最后一个字符来排序。

放回到原数组后,需要清空桶中的数据,这样,在下一趟桶排序时,将根据 字符串的 第 pos-1 个字符 来决定将该字符串放到哪个桶中去

这里待排序的字符串数目arr.length 可以大于26,因为,每个桶中(ArrayList<String>)可存储多个字符串!

 

四,桶排序复杂度分析

桶排序可以做到线性时间复杂度,比如上面的10万个人的年龄排序。将10万条年龄数据输入,复杂度是O(N),输出排序结果时遍历每个桶复杂度是O(M),故总时间复杂度是O(M+N)。而这种情况下桶的个数远远小于数据条数。

对于使用多趟桶排序的情形,时间复杂度是O(p(N+b)),其中N是输入的数据量,b是桶的个数,p是桶排序的趟数。比如上面提到的字符串排序,p是字符串的长度,N是字符串个数,b则是桶的数目(也即字符串中字符的种类(a-z),26种)

 

五,整个完整代码实现

复制代码
 1 public class BuckSort {
 2 
 3     /**
 4      * Radix sort an array of string. Assume all char are a-z (alph table)
 5      * @param arr
 6      * @param stringLen
 7      *            All have same length
 8      */
 9     public static void raidxSort(String[] arr, int stringLen) {
10         final int BUCKETS = 26;
11         ArrayList<ArrayList<String>> buckets = new ArrayList<>();
12         
13         
14         for(int i = 0; i < BUCKETS; i++)
15             buckets.add(new ArrayList<String>());
16 
17         for (int pos = stringLen - 1; pos >= 0; pos--)// 一共进行stringLen趟排序
18         {
19             for (String s : arr)
20                 buckets.get(s.charAt(pos) - 'a').add(s);// 根据比较的字符将 字符串放到相应的桶中
21 
22             int idx = 0;
23             for (ArrayList<String> listStr : buckets){ 
24                 for (String str : listStr) 
25                         arr[idx++] = str;//将桶中的数据放回到原数组中
26                 listStr.clear();//清空桶中的数据,以便下一趟排序做准备
27             }
28         }
29     }
30 
31     public static void main(String[] args) {
32         String[] arr = { "bcao", "bcrd", "cmed", "glpq" };
33         raidxSort(arr, 4);
34         for (String str : arr) {
35             System.out.println(str);
36         }
37     }
38 }
复制代码

 
对年龄进行桶排序代码实现如下:

复制代码
public class AgeBuckSort {
    public static void buckSort(int[] ages){
        int[] buck = new int[100];//create buck
        //buck sort
        for (int age : ages)
            buck[age] ++;
        
        //print sorted result
        print(buck);
    }
    
    private static void print(int[] arr){
        int val;
        for(int i = 0; i < arr.length; i++){
            val = arr[i];
            for(int j = 1; j <= val; j++)
                System.out.print(i + " ");
        }
    }
    //for test purpose
    public static void main(String[] args) {
        Random rand = new Random();
        
        int[] ages = new int[1000];
        for(int i = 0; i < ages.length; i++)
            ages[i] = rand.nextInt(100);
        buckSort(ages);
    }
}
复制代码
本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5534262.html,如需转载请自行联系原作者

 

相关文章
|
4天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
10天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
2天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
9天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
5天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
471 12
|
3天前
|
编解码 文字识别 算法
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
一张图能装下“千言万语”?DeepSeek-OCR 用视觉压缩长文本,效率提升10倍!
363 10
|
10天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
678 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
12天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
805 2