Java数据结构与算法——桶排序

DandJ 发布于2019-08-16 11:12 / 544人阅读

摘要：实际排序中，通常对每个桶中的元素继续使用其他排序算法进行排序，所以更多时候，桶排序会结合其他排序算法一起使用。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文从最简单的一个排序算法——桶排序开始，分析桶排序的实现思路，代码实现，性能特点以及适用场景。

0、其他排序算法索引(待更)

java数据结构与算法——快速排序
java数据结构与算法——插入排序

1、桶排序思想

一个简单例子：
对6个人的英语测试成绩（1~10分）进行排序。假如分数是[6,5,8,8,10,9],用桶排序的思想就是准备10个桶，编号依次为1~10，将成绩放入对应的桶中，例如6分放入6号桶，两个8分放入8号桶...然后按照桶的标号顺序逐一输出（有就输出，没有就不输出），这就是桶排序的基本思想。

事实上，这只是一个简易版，试想一下，如果待排序的元素跨度范围比较大，例如1~10000，是不是需要10000个桶？实际上这种情况下，一个桶里并非总放一个元素，很多时候一个桶里放多个元素。其实真正的桶排序和散列表有一样的原理。

实际排序中，通常对每个桶中的元素继续使用其他排序算法进行排序，所以更多时候，桶排序会结合其他排序算法一起使用。

2、桶排序代码

在分析了桶排序的思想后，首先要知道待排序元素的范围，以上述为例，声明一个长度为10的数组作为10个桶，然后将成绩逐一往桶中放时，该桶的值+1，最终输出倒序输出数组下标，数组每个位置的值为几就输出几次，这样就能实现基本的桶排序。

public class BucketSort {
    private int[] buckets;
    private int[] array;
    
    public BucketSort(int range,int[] array){
        this.buckets = new int[range];
        this.array = array;
    }
    
    /*排序*/
    public void sort(){
        if(array!=null && array.length>1){
            for(int i=0;i=0; i--){
            for(int j=0;j
测试代码：
public class SortTest {
    public static void main(String[] args) {
        testBucketsSort();
    }
    
    private static void testBucketsSort(){
        int[] array = {5,7,3,5,4,8,6,4,1,2};
        BucketSort bs = new BucketSort(10, array);
        bs.sort();
        bs.sortOut();//输出打印排序
    }
}
3、桶排序性能特点
桶排序实际上只需要遍历一遍所有的待排元素，然后依次放入指定的位置。如果加上输出排序的时间，就要遍历所有的桶。因此桶排序的时间复杂度是O(n+m),n是待排元素的个数，m是桶的个数，也就是待排元素的范围。这个算法算是相当快的排序算法了，但是空间复杂度比较大。
当待排元素的大小范围比较大，但待排元素个数比较少时，空间浪费就比较严重，待排元素分布月均匀，空间利用率越高，事实上这种情况很少见。
通过以上性能分析，可以得出桶排序的特点：速度快且简单，但同时空间利用率较低。当待排数据跨度很大时，空间利用率是无法忍受的。
4、桶排序适用场景
根据桶排序的特点，桶排序一般适用于一些特定的环境，比如数据范围较为局限或者有一些特定的要求，比如需要通过哈希映射快速获取某些值，需要统计每个数的数量。但是这一切都以确认数据的范围为前提，如果范围跨度过大，则考虑用其他算法。
其他排序算法索引(待更)
java数据结构与算法——快速排序
java数据结构与算法——插入排序
码字不易，如对您有帮助，欢迎点赞收藏打赏^_^

GPU云服务器云服务器桶排序算法桶排序 java插入排序算法 java实验排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71088.html

面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者...

Awbeci 2019-08-26 10:24 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
数据结构与算法——线性排序

摘要：实际上，桶排序的应用场景十分的有限，对数据的要求比较苛刻。极端情况下，如果数据全部划分到一个桶内，就变成了非线性排序了。 1. 回顾前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n2) 、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 O(nlogn) 的希尔排序、归并排序、快速排序。其实这几种排序都有一个特性，那就是它们都是基于数据的比较和移动...

Allen 2019-08-16 15:59 评论0 收藏0
Java数据结构与算法——插入排序

摘要：当序列本身有序时，插入排序的时间复杂度为。因为此时的分区内数据往往是近似有序的，所以使用快排并不一定优于插入排序。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中插入排序算法，包括插入排序的思路，适用场景，性能分析，java代码等 0、其他排序算法索引(待更) java数据结构与算法——快速...

骞讳护 2019-08-15 15:19 评论0 收藏0