`
endual
  • 浏览: 3560987 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

桶排序(代码自己写)

 
阅读更多

简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

  例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

  可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储  

  (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  

  100个桶。  

  然后对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  

  然后再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  

  何排序法都可以。最后依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  

  样就得到所有数字排好序的一个序列了。  

  假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

  对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

 

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

 

  从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

  当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  

  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的  

  排序了。  

需要特别注意的是桶的大小不能设置得太小,否则当随机数据堆积在一个小的范围是,会

造成桶的溢出(数组越界)

(以上代码是互联网上转来的,再次谢过)

分享到:
评论

相关推荐

    桶排序代码

    例如,提供的`BucketSort.docx`文件可能包含了桶排序的详细步骤、代码示例以及不同情况下的性能分析。通常,这样的文档会讲解如何创建和管理桶,如何选择合适的排序算法对桶内元素排序,以及如何优化桶排序的实现以...

    桶排序.py 使用python代码实现

    桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶...

    c++简单代码桶排序

    c++桶排序的代码,当初我学排序的时候也用了一些时间才想通,所以,如果一时想不通的话也别放弃,要一直坚持下去。

    桶排序 c++实现

    C++代码实现桶排序时,需要注意内存管理,避免不必要的拷贝和内存泄漏。此外,选择合适的桶大小和桶数量对性能有很大影响,这需要根据输入数据的特性进行调整。 标签中提到的"heap-sort"是指堆排序,它是另一种常用...

    桶排序算法(C++版)

    桶排序(Bucket Sort)是一种分布式排序算法,它将要排序的数据分到几个有序的桶里,每个桶再分别排序,最后按照每个桶内元素的顺序依次取出,组合...在C++中实现桶排序,可以充分利用标准库提供的工具,简化代码编写。

    桶排序介绍和java代码实现

    桶排序介绍和java代码实现 桶排序是一种线性时间复杂度的排序算法,它通过将待排序元素分配到不同的桶中,对每个桶中的元素进行排序,然后按照桶的顺序依次将元素取出,从而实现排序的目的。 桶排序的算法步骤包括...

    C++写的希尔排序 归并排序 桶排序 堆排序 3种快速排序 插入排序等

    希尔排序、归并排序、桶排序、堆排序和快速排序都是经典的计算机算法,主要用于对数据进行排序。在C++编程语言中,这些排序算法的实现是程序员必须掌握的基础技能之一。接下来,我们将深入探讨这些排序算法的工作...

    桶排序-解决排序问题

    桶排序(Bucket Sort)是一种分布式排序算法,常用于大数据处理和流式计算中。它将待排序的数据分布到多个“桶”中,每个桶再独立地进行排序,最后按照桶的顺序依次取出桶中的元素,形成有序序列。桶排序的核心思想...

    用Java实现桶排序

    ### 使用Java实现桶排序 #### 知识点概述 桶排序是一种分布式的排序算法,它将数组分到有限数量的“桶”里,然后分别对每个桶进行排序(通常是使用其他排序算法)。最后,将各个桶的数据按顺序合并起来得到最终...

    java版冒泡排序,插入排序,堆排序,快速排序,归并排序,希尔排序,桶排序

    在编程领域,排序算法是数据结构与算法学习中的基础部分,它们用于整理无序的数据序列。以下是关于Java实现的七种排序算法的详细...在Java编程中,理解这些排序算法的实现和性能特点,有助于写出高效、适应性强的代码。

    Python3实现桶排序(源代码)

    ### Python3实现桶排序(源代码)的知识点详解 #### 一、桶排序的基本概念与原理 桶排序(Bucket Sort)是一种高效的排序算法,尤其在处理具有特定分布规律的数据时表现突出。它属于非比较型排序算法之一,通过将...

    C++实现桶排序(源代码)

    ### C++实现桶排序 #### 实现原理与关键要素 桶排序是一种高效的排序算法,尤其适合数据分布较为均匀的情况。其基本思想是将输入数据按照一定规则分配到多个有序的“桶”中,随后对每个桶内的数据进行排序,最后将...

    C++排序算法对比(桶排序等)

    本文将深入探讨在C++中实现的几种主要排序算法,包括归并排序、插入排序、冒泡排序、希尔排序、快速排序以及桶排序,并对它们的原理、优缺点和适用场景进行比较。 首先,让我们逐一了解这些排序算法。 1. **归并...

    Java排序算法(桶排序,基数排序等)

    桶排序假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再单独排序,最后合并所有桶的排序结果。桶排序的时间复杂度可以达到线性O(n + k),其中k是桶的数量。Java实现如下(未给出,需自行实现)。 9. ...

    桶排序 C 语言代码实现示例

    桶排序c语言

    详解Bucket Sort桶排序算法及C++代码实现示例

    桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。...桶排序代码: /* *

    桶排序_BUCKETSORT

    提供的`bucketSort.cc`文件可能包含一个桶排序的C++实现,通过阅读源代码,你可以深入理解桶排序的具体步骤和细节,包括映射函数的设计、桶的创建和数据的分布等。 桶排序是一种非常实用的排序算法,尤其在处理大...

    排序算法-桶排序

    **桶排序(Bucket Sort)**是一种分布式的排序算法,它将待排序的数据分布到多个“桶”中,每个桶内部再分别进行排序,最后...在`桶排序.cpp`代码中,我们可以深入学习其实现细节,理解并掌握这种排序算法的工作原理。

    Java实现桶排序算法(源代码)

    ### Java实现桶排序算法 #### 实现原理与关键步骤 桶排序是一种高效的排序算法,尤其适合于处理数据分布均匀的情况。其核心思想是通过将数据分成若干个“桶”,然后分别对这些桶内的数据进行排序,最后将这些排序...

    详解Java常用排序算法-桶排序

    在上面的代码中,`bucketSort` 函数接受一个整数数组和桶的大小作为输入,并使用桶排序算法对该数组进行排序。该函数首先找到输入数组中的最小值和最大值,并计算桶的个数。然后,该函数创建一个大小为桶的个数的桶...

Global site tag (gtag.js) - Google Analytics