您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

桶排序:原理、性能分析与 Java 实现

时间:2023-10-13 13:32:29  来源:微信公众号  作者:修己xj

桶排序(Bucket Sort)是一种排序算法,通常用于将一组数据分割成有限数量的桶(或容器),然后对每个桶中的数据进行排序,最后将这些桶按顺序合并以得到排好序的数据集。

桶排序:原理、性能分析与 Java 实现图片

桶排序原理

  1. 确定桶的数量:首先,确定要使用的桶的数量。通常,桶的数量可以根据数据范围和分布情况来确定。
  2. 分发数据:将待排序的元素按照一定的规则(例如,数值大小)分发到不同的桶中。
  3. 每个桶内排序:对每个桶内的元素进行排序。这可以使用任何排序算法,例如插入排序或快速排序。
  4. 合并桶:将每个桶内的元素按照桶的顺序合并,形成有序序列。

图示如下:

桶排序:原理、性能分析与 Java 实现图片

桶排序性能分析

  • 时间复杂度:桶排序的时间复杂度取决于数据的分布情况。在最理想的情况下,当数据均匀分布在各个桶中时,每个桶内的排序时间复杂度是 ,因此总体时间复杂度为 。但在最坏情况下,如果所有数据都分布在一个桶中,桶内排序的时间复杂度可以达到 。在平均情况下,桶排序通常表现为 。
  • 空间复杂度:桶排序需要额外的存储空间来存储桶,因此空间复杂度为 ,其中 n 表示排序元素的个数,k 表示桶的数量。
  • 稳定性:桶排序通常是稳定的,即相等元素的相对顺序在排序后不会发生变化。

使用场景

桶排序适用于以下情况:

  • 数据分布相对均匀。
  • 数据范围已知,可以将数据映射到有限数量的桶中。

JAVA 代码实现

以下是使用 Java 实现桶排序的示例代码,其中每个桶中的元素排序使用的是快速排序,快速排序的详解请参考历史博文 深入了解快速排序:原理、性能分析与 Java 实现:

public class Test {

    public static void mAIn(String[] args) {
        int[] arr = new int[]{17,35,37,32,63,46,24};
        System.out.println("原始数组:"+ Arrays.toString(arr));
        bucketSort(arr);
        System.out.println("排序后的数组:"+ Arrays.toString(arr));
    }



    //桶排序
    public static void bucketSort(int[] arr){

        int maxVal = Arrays.stream(arr).max().getAsInt();
        int minVal = Arrays.stream(arr).min().getAsInt();

        //计算桶的数量,+1 是保证至少有1个桶来装数据
        int bucketCount  = (maxVal - minVal)/arr.length + 1;

        // 用于存储每个桶中元素的出现次数
        int[] order = new int[bucketCount];
        // 用于存储每个桶中的数据
        int[][] output = new int[bucketCount][arr.length];

        int len = arr.length;

        //每个桶中数据的范围,+1 是至少每个桶中的数据范围为1
        int rang =  (maxVal - minVal)/bucketCount +1;

        //将待排序的数组中的所有元素放入到桶中
        for(int i = 0; i < len; i++ ){
            //计算数组元素所在的桶
            int index = (arr[i] - minVal)  /  rang ;
            //将元素放入指定的桶
            output[index][order[index]] = arr[i];
            //添加桶元素的计数
            order[index]++;
        }

        System.out.println("桶计数数组为:"+ Arrays.toString(order));

        int k = 0;

        //遍历桶,将桶中的元素放入源数组中,并对其进行快速排序
        for(int i = 0; i < bucketCount; i++){
            int j ;
            if(order[i] > 0){
                // 将桶中的元素放入源数组中
                for(j = 0; j < order[i]; j++){
                    arr[k++] = output[i][j];
                }
                //对桶中的元素进行快速排序
                quickSort(arr,k-j,k-1);
            }

        }
    }


    //快速排序的详解请参考历史博文 `深入了解快速排序:原理、性能分析与 Java 实现`
    public static void quickSort(int[] arr,int left,int right) {

        //递归结束条件left < right
        if(left < right){
            // 通过分区函数得到基准元素的索引
            int pivotIndex = partition(arr, left, right);
            //递归对基准元素左边的子数组进行快速排序
            quickSort(arr,left,pivotIndex-1);
            //递归对基准元素右边的子数组进行快速排序
            quickSort(arr,pivotIndex+1,right);
        }
    }

    public static int partition(int[] arr,int left,int right) {
        // 选择最后一个元素作为基准元素
        int pivot = arr[right];
        int i = left;

        //循环数组,如果满足条件,则将满足条件的元素交换到arr[i],同时i++,循环完成之后i之前的元素则全部为小于基准元素的元素
        for (int j = left; j < right; j++) {
            if(arr[j] < pivot){
                if(j != i){
                    int temp  = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                i++;
            }
        }

        // 交换 arr[i] 和基准元素
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;

        //返回基准元素的下标
        return i;
    }
}

输出结果为:

原始数组:[17, 35, 37, 32, 63, 46, 24]
桶计数数组为:[1, 1, 3, 0, 1, 0, 1]
排序后的数组:[17, 24, 32, 35, 37, 46, 63]

这是一个基本的桶排序实现示例。您可以根据实际需求和数据类型进行扩展和优化。

总结

总的来说,桶排序是一种简单但有效的排序算法,特别适用于某些特定范围内数据的排序,当数据分布均匀时,性能较好。然而,对于不均匀分布的数据,其性能可能下降,因此在实际应用中需要谨慎选择。



Tags:桶排序   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
桶排序:原理、性能分析与 Java 实现
桶排序(Bucket Sort)是一种排序算法,通常用于将一组数据分割成有限数量的桶(或容器),然后对每个桶中的数据进行排序,最后将这些桶按顺序合并以得到排好序的数据集。图片桶排序原理 ...【详细内容】
2023-10-13  Search: 桶排序  点击:(193)  评论:(0)  加入收藏
桶排序—如何根据年龄给100万用户数据排序
如何确定桶的 区间范围,有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量,除最后一个桶只包含数列最大值外, 前面各个桶的区间按照比例来确定。一、定义桶排序...【详细内容】
2023-03-09  Search: 桶排序  点击:(132)  评论:(0)  加入收藏
桶排序算法
桶排序算法就是把数据平分到每一个桶中,然后对桶中的数据进行排序,再按桶的顺序依次倒出数据,桶排序算法很好理解。桶排序算法也是以空间换时间的算法。举例说明一下桶排序算法...【详细内容】
2022-03-24  Search: 桶排序  点击:(320)  评论:(0)  加入收藏
两分钟彻底搞懂桶排序
前言在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,算法的排序中,我们...【详细内容】
2021-03-17  Search: 桶排序  点击:(600)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(12)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(50)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(44)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(73)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(89)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(62)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(107)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(164)  评论:(0)  加入收藏
站内最新
站内热门
站内头条