首页 > 编程语言 >桶排序算法及其Java实现

桶排序算法及其Java实现

时间:2023-07-03 21:33:53浏览次数:53  
标签:arr Java 每个 int 算法 num 数组 排序

桶排序是一种排序算法,它的原理是将数组分到有限数量的桶里,每个桶再个别排序,最后依次把各个桶中的记录列出来。桶排序的效率取决于映射函数的选择和桶的数量。桶排序适用于数据分布比较均匀,或者比较侧重于区间数量的情况。

下面是我为你写的博客正文,希望对你有帮助:

桶排序算法及其Java实现

什么是桶排序?

桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后依次把各个桶中的记录列出来1

桶排序是计数排序的变种,它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。把计数排序中相邻的m个”小桶”放到一个”大桶”中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果2

桶排序的步骤

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

桶排序的示例

假设我们有一个数组 arr = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109],我们想要对它进行升序排列。我们可以按照以下步骤进行桶排序:

  1. 首先,我们需要确定数组中的最大值和最小值,以及每个桶的大小。在这个例子中,最大值是194,最小值是13,我们可以设置每个桶的大小为10,那么我们就需要(194-13)/10+1=19个桶。
  2. 然后,我们需要创建一个长度为19的数组 buckets,每个元素是一个空列表,用来存放对应范围内的元素。例如,buckets[0]存放[13,23)之间的元素,buckets1存放[23,33)之间的元素,以此类推。
  3. 接着,我们遍历原始数组 arr,根据每个元素值和最小值之差除以桶大小得到它应该放入哪个桶中。例如,63应该放入(63-13)/10=5号桶中,189应该放入(189-13)/10=17号桶中。我们将每个元素按照这个规则插入到对应的桶中。
  4. 然后,我们对每个非空的桶中的元素进行排序。我们可以使用任何一种比较排序算法,例如插入排序、快速排序等。在这里,我们假设使用插入排序。
  5. 最后,我们按照顺序遍历所有的桶,并将每个桶中的元素依次放回原始数组 arr 中。这样,我们就完成了对 arr 的升序排列。

下面是桶排序的过程图示:

 

桶排序的代码实现

下面是使用Java语言实现的桶排序算法,其中使用了插入排序对每个桶进行排序:

public class BucketSort {

    //插入排序
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    //桶排序
    public static void bucketSort(int[] arr) {
        //确定数组中的最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }
        //确定每个桶的大小和数量
        int bucketSize = 10;
        int bucketCount = (max - min) / bucketSize + 1;
        //创建桶数组,每个元素是一个列表
        List<Integer>[] buckets = new List[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        //将原始数组中的元素按照映射规则放入对应的桶中
        for (int num : arr) {
            int index = (num - min) / bucketSize;
            buckets[index].add(num);
        }
        //对每个非空的桶进行排序,并将结果放回原始数组中
        int k = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                //将列表转换为数组,方便使用插入排序
                int[] bucketArr = new int[bucket.size()];
                for (int i = 0; i < bucket.size(); i++) {
                    bucketArr[i] = bucket.get(i);
                }
                //对每个桶进行排序
                insertionSort(bucketArr);
                //将每个桶中的元素放回原始数组中
                for (int num : bucketArr) {
                    arr[k++] = num;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109};
        System.out.println("原始数组:" + Arrays.toString(arr));
        bucketSort(arr);
        System.out.println("排序后的数组:" + Arrays.toString(arr));
    }
}

桶排序的复杂度分析

时间复杂度

桶排序的平均时间复杂度是 O(n + k),其中 n 是待排序数组的长度,k 是桶的数量。这是在假设输入数据服从均匀分布,且每个桶中的数据可以用 O(1) 的时间进行排序(例如用计数排序)的情况下得到的。如果输入数据不服从均匀分布,或者每个桶中的数据需要用比较排序算法进行排序,那么桶排序的时间复杂度会变化。最好情况下,如果所有数据都被分配到了一个桶中,那么只需要对这个桶进行一次排序,时间复杂度为 O(n);最坏情况下,如果所有数据都被分配到了不同的桶中,那么需要对 n 个桶进行 n 次排序,时间复杂度为 O(n^2)。

空间复杂度

桶排序的空间复杂度是 O(n + k),其中 n 是

空间复杂度是指算法在执行过程中所需的额外空间。桶排序需要创建一个长度为 k 的桶数组,每个桶中可能存放多个元素,因此桶排序需要的额外空间与输入数据的规模 n 和桶的数量 k 有关。一般来说,k 越大,每个桶中的元素越少,空间利用率越高;k 越小,每个桶中的元素越多,空间浪费率越高。最好情况下,如果所有数据都被分配到了一个桶中,那么只需要一个桶,空间复杂度为 O(n);最坏情况下,如果所有数据都被分配到了不同的桶中,那么需要 n 个桶,空间复杂度为 O(n + n) = O(2n)。

桶排序的优缺点

优点

  • 桶排序是一种稳定的排序算法,即相同值的元素在排序后仍然保持原来的相对顺序。
  • 桶排序可以利用多核处理器或分布式系统进行并行计算,提高排序效率。只需要将不同的桶分配给不同的处理器或机器进行排序即可。
  • 桶排序可以根据实际情况选择合适的映射函数和桶大小,以达到最佳的性能。

缺点

  • 桶排序需要额外的空间来存放桶和桶中的元素,空间复杂度较高。
  • 桶排序对输入数据的分布有一定的要求,如果数据分布不均匀,或者映射函数不合理,那么桶排序的效率会降低。
  • 桶排序需要对每个桶进行排序,如果每个桶中的元素较多,那么还需要使用其他的排序算法,增加了实现的复杂度。

总结

桶排序是一种基于分治思想和映射函数的排序算法,它将待排序数组分到有限数量的桶里,每个桶再分别排序,最后依次把各个桶中的记录列出来。桶排序适用于数据分布比较均匀,或者比较侧重于区间数量的情况。桶排序是一种稳定的排序算法,它可以利用多核处理器或分布式系统进行并行计算,提高排序效率。但是桶排序也有一些缺点,它需要额外的空间来存放桶和桶中的元素,空间复杂度较高。而且它对输入数据的分布有一定的要求,如果数据分布不均匀,或者映射函数不合理,那么桶排序的效率会降低。另外,它还需要对每个桶进行排序,如果每个桶中的元素较多,那么还需要使用其他的排序算法,增加了实现的复杂度。

标签:arr,Java,每个,int,算法,num,数组,排序
From: https://www.cnblogs.com/shoshana-kong/p/17524140.html

相关文章

  • 汇报 第二周第二天 JAVA方法
    今日所学:掌握定义Java方法时的语法格式及各个参数的作用;掌握方法的有无返回值的两种情况的处理方式;掌握方法的参数是值参数、引用参数或者不定长参数的使用方法;明确方法的重载和使用方法 明日计划:JAVA中的面向对象编程遇到困难:练车真坐牢......
  • JavaScript(四)面向对象
    创建对象prototype对象JavaScript对每个创建的对象都会设置一个原型,指向它的原型对象。当我们用obj.xxx访问一个对象的属性时,JavaScript引擎先在当前对象上查找该属性,如果没有找到,就到其原型对象上找,如果还没有找到,就一直上溯到Object.prototype对象,最后,如果还没有找到,就只能返......
  • JAVA调用ABAP RFC接口-DEMO
    packagecom.swift.oa;importcom.sap.conn.jco.*;/***@Author:Wriprin*@Date:2022/11/2517:20*@Version1.0*/publicclassGetMaraInfo{publicstaticvoidmain(String[]args)throwsJCoException{//ConfigurationofSAPconnec......
  • JavaScript(三)Array的高阶函数
    map、reducemap:map()方法定义在JavaScript的Array中,接收一个函数对象作为参数,函数定义运算规则,对array中的每个元素进行运算,结果是一个新的array。functionpow(x){returnx*x;}vararr=[1,2,3,4,5,6,7,8,9];varresults=arr.map(pow);//[1,4,9......
  • JavaScript(一)基础
    JS引入到文件嵌入到html文件中,在<header>或<body>中使用<script><script> vari=10; console.log(i);</script>引入JS文件,在<header>或<body>中使用<script><scriptsrc="./index3_script.js"type="text/j......
  • 暑假Java学习第二周——第二天
    7.3键盘录入及录入求和:importjava.util.Scanner;publicclassTest{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);System.out.println("请输入第一个数字");inti1=sc.nextInt();System.out.println("请输入第二个数字");inti2=sc.nex......
  • 如何在JAVA后端实现跨域请求
     1.  什么是跨域请求 跨域请求是指浏览器向不同域名的服务器发送请求,例如从http://www.a.com向http://www.b.com发送请求。由于浏览器的同源策略,跨域请求会受到限制,需要服务器端或客户端进行处理。同源策略是为了保证用户信息的安全,防止恶意的网站窃取数据。举例说明:假......
  • Java框架中常用的几种成熟的token生成框架对比
    Java框架中常用的几种成熟的token生成框架有:SpringSecurity:一个基于Spring的安全框架,提供了声明式的安全访问控制解决方案,支持多种认证和授权机制,如OAuth2.0、JWT等。ApacheShiro:一个轻量级的Java安全框架,提供了身份认证、授权、加密、会话管理等功能,支持多种数据源和缓存实......
  • 数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。
    数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。图算法,搜索算法等算法码源见文末1.算法目录18大DM算法包名目录名算法名AssociationAnalysisDataMining_AprioriApriori-关联规则挖掘算法AssociationAnalysisDataMining_FP......
  • Idea 根据表结构生成 java 实体
    Idea根据表结构生成java实体  1、配置mysql 2、在连接后的任意一张表上右键,修改脚本 修改GeneratePOJOs.groovyimportcom.intellij.database.model.DasTableimportcom.intellij.database.model.ObjectKindimportcom.intellij.database.util.Caseimport......