美文网首页
C语言必学的12个排序算法:计数排序(第9篇)

C语言必学的12个排序算法:计数排序(第9篇)

作者: 哪有岁月静好 | 来源:发表于2020-08-04 16:23 被阅读0次

题外话计数排序时间性能比之前的排序算法高,在实际中应用较多,只需要O(n)时间即可完成排序。计数排序思想比较巧妙,建议大家对照课本多学习,本文主要给出能运行的实例程序。

[C语言必学的12个排序算法:基础知识 (第0篇)]

线性时间排序

之前学习的快速排序、堆排序、归并排序都是一类基于比较的排序算法,需要通过比较关键字大小确定数据元素的位置。这类算法最优的时间复杂度只能到O(nlogn)。

线性时间排序是一类非比较排序算法,时间复杂度O(n),不需要通过比较关键字大小即可完成排序。计数排序(counting sort)是其中一种。

计数排序基本思想

基本思想是给定一个待排的整数序列,对于每一个数据元素,直接存放在保存排序结果的数组对应下标的位置,例如数据元素为5时,直接存放到数组a[5]位置,数据元素为0时,直接存放到数组a[0]的位置。这样利用待排的数据元素和数组内存地址位置建立一一对应关系,由于数组内存分配是从小到大连续分配,因此最后直接输出数组,即可获得有序的整数序列。

计数排序对于输入的数据元素类型有要求,一般是小范围的整数或字符,或者很方便利用数据元素本身和内存地址建立意义对应关系。对于n个整数输入序列,确定每个数据元素取值范围[0-k],当k值小于等于n时,其时间复杂度是O(n),需要的辅助空间是O(k),当n很小也就是数据量很小,但是n取值范围很大也就是k值很大时,不适合使用计数排序,因为内存空间浪费严重,时间复杂度也变成O(k)。

考虑到待排数据记录关键字有重复,会出现多次,为保证排序结果的稳定性,因此计数排序需要对出现多次关键字的数据进行计数,保存到数组对应下标的位置,并且根据该数组计数进一步计算其在排序后的序列的位置。

代码实现

本实例代码实现要点:

1.数组a[]保存待排的整数数据记录,数据记录本身就是关键字,每个整数的取值范围[0-k],最大取值为k。

2.数组c[]临时保存每个整数出现的次数,如果没有出现值为0,利用内存动态分配,大小为k。

3.数组b[]用来临时保存排序后的整数数据记录,最终将数组b[]的排序结果复制到数组a[],方便封装使用。

3.对数组c[]的计数进行累加统计,从而确定每个数据元素在数组b[]的位置,特别是重复出现的数据,在数组b[]中将是一段位置。

/*
#include <stdio.h>
#include <stdlib.h>


void counting_sort(int a[], int length, int k)
{
  // 使用calloc会自动初始化为0
  // 数组b临时保存排序后的数据记录 
  int *b = (int *)calloc(length, sizeof(int));
  // 数组c对数据记录关键字进行计数 
  int *c = (int *)calloc(k, sizeof(int));
  
  int i;
  // 每出现1个数据记录,对应的数组位置+1 
  // c[i]表示数据等于i的元素个数 
  for(i=0; i<length; i++)
    c[a[i]] = c[a[i]] + 1;
  
  // 对数组C的计数累累加确定排序后位置
  // c[i]表示小于等于i值的数据元素个数
  for(i=1; i<k; i++)
    c[i] = c[i] + c[i-1]; 
  
  // 将排序结果输出到临时数组b中
  for(i=length-1; i>=0; i--)
  {
    // 注意数组b数组下标从0开始
    // 计算的实际位置-1 
    b[c[a[i]]-1] = a[i];
    // 如果数据元素重复出现 
    // 将该元素下一个保存位置前移 
    c[a[i]] = c[a[i]] - 1;
  } 
  
  // 复制到数组a中
  for(i=0; i<length; i++)
    a[i] = b[i]; 
  
  free(b);
  free(c);
}
int main(void)
{
    int a[14] = {4,3,1,2,6,5,0,9,8,7,1,3,0,1};
    counting_sort(a, 14, 10);
    int i;
    for(i=0; i<14; i++)
      printf("%d ", a[i]);
    return 0;
}

其实做为一个学习者,有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。



相关文章

  • 一文弄懂计数排序算法!

    这是小川的第385次更新,第413篇原创 01 计数排序算法概念 计数排序不是一个比较排序算法,该算法于1954年...

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • C语言必学的12个排序算法:计数排序(第9篇)

    题外话计数排序时间性能比之前的排序算法高,在实际中应用较多,只需要O(n)时间即可完成排序。计数排序思想比较巧妙,...

  • 有关iOS基础知识总结

    1.C语言 排序算法)(数组的大小排序,字母的先后排序,单词的计数) 2.面向过程和面向对象 面向过程:分析出解决...

  • c语言排序算法

    c语言排序算法

  • 排序算法-8---计数排序

    # 排序算法-8---计数排序 概念 计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于...

  • 算法and数据结构

    算法 冒泡排序 选择排序 计数排序

  • 常用排序算法总结9一一计数排序

    定义 计数排序(英语:Counting Sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C,其中...

  • 排序算法

    常见排序算法 本文涉及的算法有:冒泡排序选择排序计数排序 冒泡排序 伪代码 流程图 选择排序 伪代码 流程图 计数...

  • 08-计数排序(Counting Sort)

    计数排序(Counting Sort) 本节内容,继续介绍排序算法,在本节内容之前,介绍过7种排序算法,那计数排序...

网友评论

      本文标题:C语言必学的12个排序算法:计数排序(第9篇)

      本文链接:https://www.haomeiwen.com/subject/ftxbrktx.html