详解计数排序算法及C语言程序中的实现

关于计数排序算法

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量内存。计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

算法的步骤如下：

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  • 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

代码示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
  int *C=new int[K+1];
  int i;
  memset(C,0,sizeof(int)*(K+1));
  for (i=1;i<=N;i++) //把A中的每个元素分配
    C[A[i]]++;
  for (i=2;i<=K;i++) //统计不大于i的元素的个数
    C[i]+=C[i-1];
  for (i=N;i>=1;i--)
  {
    B[C[A[i]]]=A[i]; //按照统计的位置，将值输出到B中，将顺序输出到Order中
    Order[C[A[i]]]=i;
    C[A[i]]--;
  }
}
int main()
{
  int *A,*B,*Order,N=15,K=10,i;
  A=new int[N+1];
  B=new int[N+1];
  Order=new int[N+1];
  for (i=1;i<=N;i++)
    A[i]=rand()%K+1; //生成1..K的随机数
  printf("Before CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",A[i]);
  CountingSort(A,B,Order,N,K);
  printf("\nAfter CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",B[i]);
  printf("\nOrder:\n");
  for (i=1;i<=N;i++)
    printf("%d ",Order[i]);
  return 0;
}
赞 (0)

相关推荐

  • C语言演示对归并排序算法的优化实现

    基础 如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组.归并排序便是建立在这一基础上.要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序.子数组的排序同样采用这样的方法排序,这个过程是递归的. 下面是示例代码: #include "timsort.h" #include <stdlib.h> #include <string.h> // 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个 // 已排序

  • 举例讲解C语言对归并排序算法的基础使用

    基础概念 百度百科是这么描述归并排序的: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作. 设有数列 {6,202,100,301,38,8,1} 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计: 1

  • 简单了解C语言中直接插入排序与直接选择排序实现

    直接插入排序 基本思路: 1. 从a[0]开始,也就是从1个元素开始是有序的,a[1]~a[n-1]是无序的. 2. 从a[1]开始并入前面有序的数组,直到n-1. #include <stdio.h> #define N 5 void insertsort(int a[], int n); void swap(int *x, int *y); void insertsort(int a[], int n){ int i,j; for(i=1; i<n; i++){ for(j=i; j

  • C语言实现基于最大堆和最小堆的堆排序算法示例

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

  • 希尔排序算法的C语言实现示例

    希尔排序算法的C语言实现示例

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几

  • C语言中使用快速排序算法对元素排序的实例详解

    C语言中使用快速排序算法对元素排序的实例详解

    调用C语言的快速排序算法qsort(); #include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 100 //从小到大排序 int comp1(const void *x,const void *y) { return *(int *)x - *(int *)y; } //从大到小排序 int comp2(const void *x,const void *y) { return *(in

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

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

  • 深入解析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语言版代码示例

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

  • 详解计数排序算法及C语言程序中的实现

    关于计数排序算法 当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k).计数排序不是比较排序,排序的速度快于任何比较排序算法. 由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量内存.计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名.但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组. 算法的步骤如下: 找出待排序的数组中最大

  • 详解如何愉快的在微信小程序中使用SVG图标

    SVG近几年因各种优势被大量的应用,遗憾的是到目前为止微信小程序并不支持以XML的形式使用SVG,这使得SVG的灵活性大大下降,大多数人选择放弃在微信小程序中使用SVG图标方案. 那么,真的就没有办法在微信小程序中愉快的使用SVG图标了吗?我们先来分析一下,对于使用SVG图标我们有哪些需求: 能够引入使用 能够调整颜色 首先第一点是没有问题的,微信小程序支持以Image.src的形式引入SVG.接下来就是本文的重点部分了,如何让使Image形式的SVG可以改变颜色. 在最近对CSS的学习中,我发

  • 详解桶排序算法的思路及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++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • 详解Python排序算法的实现(冒泡,选择,插入,快速)

    详解Python排序算法的实现(冒泡,选择,插入,快速)

    目录 1. 前言 2. 冒泡排序算法 2.1 摆擂台法 2.2 相邻两个数字相比较 3. 选择排序算法 4. 插入排序 5. 快速排序 6. 总结 1. 前言 所谓排序,就是把一个数据群体按个体数据的特征按从大到小或从小到大的顺序存放. 排序在应用开发中很常见,如对商品按价格.人气.购买数量……显示. 初学编程者,刚开始接触的第一个稍微有点难理解的算法应该是排序算法中的冒泡算法. 我初学时,“脑思维”差点绕在 2 个循环结构的世界里出不来了.当时,老师要求我们死记冒泡的口诀,虽然有点搞笑,但是当

  • Python实现的计数排序算法示例

    Python实现的计数排序算法示例

    本文实例讲述了Python实现的计数排序算法.分享给大家供大家参考,具体如下: 计数排序是一种非常快捷的稳定性强的排序方法,时间复杂度O(n+k),其中n为要排序的数的个数,k为要排序的数的组大值.计数排序对一定量的整数排序时候的速度非常快,一般快于其他排序算法.但计数排序局限性比较大,只限于对整数进行排序.计数排序是消耗空间发杂度来获取快捷的排序方法,其空间发展度为O(K)同理K为要排序的最大值. 计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数,则可以确定这个数的位置

  • 详解C++图搜索算法之双端队列广搜

    详解C++图搜索算法之双端队列广搜

    目录 广度优先遍历 双端队列BFS 例题:AcWing 175. 电路维修 解题思路 AC代码 广度优先遍历 广度优先遍历是一种按照层次顺序进行访问的方法,它具有以下两种重要性质: 在访问完所有第i层的结点后,才会去访问第i+1层的结点 任意时刻,队列中至多有两个层次的结点.若其中一部分结点属于第i层,则另一部分结点属于第i+1层,并且所有第i层结点排在第i+1层之前.也就是说,广度优先遍历队列中的元素关于层次满足 双端队列BFS 在最基本的广度优先搜索中,每次沿着分支的扩展都记为“一步”,我们

  • 详解Java Bellman-Ford算法原理及实现

    详解Java Bellman-Ford算法原理及实现

    目录 一 点睛 二 算法步骤 三 算法实现 四 测试 一 点睛 如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径.该算法的优点是变的权值可以是负数.实现简单,缺点是时间复杂度过高.但是该算法可以进行若干种优化,以提高效率. Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础.Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作:而 Bellman-Ford 算法对所有边

  • 图文详解牛顿迭代算法原理及Python实现

    图文详解牛顿迭代算法原理及Python实现

    目录 1.引例 2.牛顿迭代算法求根 3.牛顿迭代优化 4 代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何计算函数零点x0 在数学上我们如何处理这个问题? 最简单的办法是解方程f(x)=0,在代数学上还有著名的零点判定定理 如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)⋅f(b)<0,那么函数y=f(x)在区间(a,b)内有零点,即至少存在一个c∈(a,b),使得f(c)=0,这个c也就是方程f(x)=0的根. 然而,数学上的方法并不一定

  • C语言程序中结构体的内存对齐详解

    目录 一.为什么存在内存对齐 二.结构体的内存对齐四规则 三.举例 一.为什么存在内存对齐 1.平台原因(移植原因): 不是所有的硬件平台都能访问任意地址上的任意数据的:某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常. 2. 性能原因: 数据结构(尤其是栈)应该尽可能地在自然边界上对齐. 原因在于,为了访问未对齐的内存,处理器需要作两次内存访问:而对齐的内存访问仅需要一次访问. 总的来说结构体的内存对齐是拿空间来换取时间的做法. 二.结构体的内存对齐四规则 默认情况:默认的对

随机推荐