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

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

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

桶排序图文示例
桶排序代码：

/*
 * 桶排序
 *
 * 参数说明：
 *   a -- 待排序数组
 *   n -- 数组a的长度
 *   max -- 数组a中最大值的范围
 */
void bucket_sort(int a[], int n, int max)
{
  int i, j;
  int *buckets;

  if (a==NULL || n<1 || max<1)
    return ;

  // 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
  if ((buckets=(int *)malloc(max*sizeof(int)))==NULL)
    return ;
  memset(buckets, 0, max*sizeof(int));

  // 1. 计数
  for(i = 0; i < n; i++)
    buckets[a[i]]++; 

  // 2. 排序
  for (i = 0, j = 0; i < max; i++)
    while( (buckets[i]--) >0 )
      a[j++] = i;

  free(buckets);
}

说明：
bucketSort(a, n, max)是作用是对数组a进行桶排序，n是数组a的长度，max是数组中最大元素所属的范围[0,max)。
假设a={8,2,3,4,3,6,6,3,9}, max=10。此时，将数组a的所有数据都放到需要为0-9的桶中。如下图：

在将数据放到桶中之后，再通过一定的算法，将桶中的数据提出出来并转换成有序数组。就得到我们想要的结果了。

赞 (0)

相关推荐

  • Objective-C实现冒泡排序算法的简单示例

    简介 冒泡算法是一种基础的排序算法,这种算法会重复的比较数组中相邻的两个元素.如果一个元素比另一个元素大(小),那么就交换这两个元素的位置.重复这一比较直至最后一个元素.这一比较会重复n-1趟,每一趟比较n-j次,j是已经排序好的元素个数.每一趟比较都能找出未排序元素中最大或者最小的那个数字.这就如同水泡从水底逐个飘到水面一样.冒泡排序是一种时间复杂度较高,效率较低的排序方法.其空间复杂度是O(n). 1, 最差时间复杂度 O(n^2) 2, 平均时间复杂度 O(n^2) 实现思路 1,每一趟比

  • 详解桶排序算法的思路及C++编程中的代码实现

    详解桶排序算法的思路及C++编程中的代码实现

    算法思路理解 我自己的理解哈,可能与网上说的有一些出入,大体都是同样的原理 无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等) 例如待排数字 [6 2 4 1 5 9] 准备10个空桶,最大数个空桶 [6 2 4 1 5 9] 待排数组 [0 0 0 0 0 0 0 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在) 1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[

  • C/C++实现八大排序算法汇总

    C/C++实现八大排序算法汇总

    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1. 插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已

  • JavaScript希尔排序、快速排序、归并排序算法

    以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

  • 深入解析Radix Sort基数排序算法思想及C语言实现示例

    基本思想: 将待排数据中的每组关键字依次进行桶分配. 具体示例: 278.109.063.930.589.184.505.269.008.083 我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2. 然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列. 930.063.083.184.505.278.008.109.58

  • 解读堆排序算法及用C++实现基于最大堆的堆排序示例

    解读堆排序算法及用C++实现基于最大堆的堆排序示例

    1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

  • 简单掌握桶排序算法及C++版的代码实现

    桶排序介绍 桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里. 假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX).在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0:将容量为MAX的桶数组中的每一个单元都看作一个"桶". 在排序时,逐个遍历数组a,将数组a的值,作为"桶数组r"的下标.当a中数据被读取时,就将桶的值加1.例如,读取到数组a[3]=5,则将r[5]的值+1. C++实现算法 假设数

  • 图文详解Heap Sort堆排序算法及JavaScript的代码实现

    图文详解Heap Sort堆排序算法及JavaScript的代码实现

    1. 不得不说说二叉树 要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree).二叉树常被用于实现二叉查找树和二叉堆. 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒.二叉树的第 i 层至多有 2i - 1 个结点:深度为 k 的二叉树至多有 2k - 1 个结点:对任何一棵二叉树 T,如果

  • 桶排序算法的理解及C语言版代码示例

    理解: 桶排序是计数排序的变种,把计数排序中相邻的m个"小桶"放到一个"大桶"中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果. 基本思想: 桶排序假设序列由一个随机过程产生,该过程将元素均匀而独立地分布在区间[0,1)上.我们把区间[0,1)划分成n个相同大小的子区间,称为桶.将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. 效率分析: 桶排序的平均时间复杂度为线性的

  • C语言选择排序算法及实例代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

随机推荐