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

2024-10-05 15:57:30

理解：
桶排序是计数排序的变种，把计数排序中相邻的m个"小桶"放到一个"大桶"中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。
基本思想：
桶排序假设序列由一个随机过程产生，该过程将元素均匀而独立地分布在区间[0,1)上。我们把区间[0,1)划分成n个相同大小的子区间，称为桶。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中，需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。
效率分析：
桶排序的平均时间复杂度为线性的O(N+C)，其中C为桶内快排的时间复杂度。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
桶排序的缺点是如果只排几个数，但是数字的范围却非常大（10个数，数的范围再0~10000000），那么我们需要10000001个桶才可以，即便是10个数。

举例
问题1：随机输入 5 个数，从大到小输出。
思路：借助一个根据输入数字最大值和最小值的范围数组，每当输入一个数字的时候，将数字插入对应数组的序号。

#include <stdio.h>
int main()
{
 int a[11],i,j,t;
 //初始化桶数组
 for(i=0;i<=10;i++)
 {
   a[i] = 0;
 }
 //循环读入5个数
 for(i = 1;i<=5;i++)
 {
   //把每一个数读到变量中去
   scanf("%d",&t);
   //计数
   a[t]++;
 }
 //从大到小输出
 for(i = 10;i>=0;i--)
 {
   for(j=1;j<=a[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 //getchar()用来暂停程序，以便查看程序输出的内容
 //也可以用system("pause");来代替
 return 0;
}

问题2：对0-1000的整数进行排序

#include<stdio.h>
int main()
{
 int book[1001],i,j,t;
 //初始化桶数组
 for(i=0;i<=1000;i++)
 {
   book[i] = 0;
 }
 //输入一个数n，表示接下来有n个数
 scanf("%d",&n);
 for(i = 1;i<=n;i++)
 {
   //把每一个数读到变量中去
   scanf("%d",&t);
   //计数
   book[t]++;
 }
 //从大到小输出
 for(i = 1000;i>=0;i--)
 {
   for(j=1;j<=book[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 return 0;
}

常用排序算法的C语言版实现示例整理

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.其确切定义如下: 输入:n个记录R1,R2,-,Rn,其相应的关键字分别为K1,K2,-,Kn. 输出:Ril,Ri2,-,Rin,使得Ki1≤Ki2≤-≤Kin.(或Ki1≥Ki2≥-≥Kin). 排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量.基本的排序算法有如下几种:交换排序(冒泡排序.快速排序).选择排序(直接选择排序.堆排序).插入排序(直接插入排序.希尔排序).归并排序.分配排序(基数排
C语言基本排序算法之shell排序实例

本文实例讲述了C语言基本排序算法之shell排序.分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*------------------------------------------------------------------------------------- Shell_sort.h shell排序是对直接插入方法的改进,它并不是对相邻元素进行比较,而是对一定间隔的元素比较. 选择增量序列的几种方法:(为方便,本例采用第一种增量序列) 1. h[1]=
C语言基本排序算法之插入排序与直接选择排序实现方法

本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------
C语言实现排序算法之归并排序详解

排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i
C语言实现归并排序算法

C语言实现归并排序算法归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序算法描述归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾
C语言冒泡排序算法详解及实例

C语言冒泡排序算法冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序.尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的. 冒泡排序是与插入排序拥有相等的执
C语言基本排序算法之桶式排序实例

本文实例讲述了C语言基本排序算法之桶式排序.分享给大家供大家参考,具体如下: 桶式排序是对一个有n个整型元素的数组a[n],其中对任意i,0 <= a[i] <= m的特殊排序算法. 可以对 n==m, n != m分别处理.写代码时需要注意的的是a[i]是访问第i-1个元素,而非第i个. /************************************************************************************/ /* Bucket_Sort.h
c语言快速排序算法示例代码分享

步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat
C语言排序算法之冒泡排序实现方法【改进版】

本文实例讲述了C语言排序算法之冒泡排序实现方法.分享给大家供大家参考,具体如下: 冒泡排序和改进的冒泡排序 /*------------------------------------------------------------------------------------------- Bubble_sort.h 冒泡排序: 时间复杂度为O(N^2) 改进的冒泡排序: 时间复杂度仍为O(N^2) 一般的冒泡排序方法有可能会在已经排好序的情况下继续比较,改进的冒泡排序设置了一个哨兵fla
C语言实现基于最大堆和最小堆的堆排序算法示例

堆定义堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

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

相关推荐

随机推荐