排序算法之八:计数排序

简介: 排序算法之八:计数排序

1.计数排序思想

计数排序,顾名思义就是计算数据的个数

计数排序又称非比较排序

思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 操作步骤:

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(范围)

2.计数排序过程

首先统计每个数据出现了多少次

假设有这么一个数组,下面的数组就是统计数据个数的

如果1出现,则对1位置++,如果3出现,则对3位置++,即

这里的代码核心稍微比较抽象,是在统计a数组中数据个数

接下来的操作是这样,对比count数组,0出现了0次,那就是0个0,1出现了3次,那就是3个1,其余同理,图示如下:

对比下来效率是非常高的,遍历一遍数组

同样,他也有局限性:

  1. 不适合分散的数据,更适合集中的数据
  2. 不适合浮点数、字符串、结构体数据排序,只适合整数

3.实现代码

求最大值max和最小值min,然后遍历原数组统计次数,最后排序

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];
  for (int i = 1; i < n; i++)
  {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  int range = max - min + 1;
  int* count = (int*)calloc(range, sizeof(int));
  if (count == NULL)
  {
    printf("calloc fail!");
    return;
  }
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
  int i = 0;
  for (int j = 0; j < range; j++)
  {
    while (count[j]--)
    {
      a[i++] = j + min;
    }
  }
}
int main()
{
  int a[] = { 10,11,10,11,15,1,2,3,5,4,2,1,0 };
  int n = sizeof(a) / sizeof(a[0]);
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  CountSort(a, n);
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}


相关文章
|
算法 搜索推荐 Python
Python算法——计数排序
Python算法——计数排序
78 0
|
1月前
|
搜索推荐 Java Go
深入了解计数排序算法
深入了解计数排序算法
34 4
|
5月前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
4月前
|
存储 算法 搜索推荐
|
11月前
|
算法 搜索推荐 大数据
【算法】排序——归并排序和计数排序
上两篇文章讲解了插入排序、选择排序以及交换排序,每种类型的排序大类下都有一到两种排序,今天给大家带来的是归并排序,和前面几种排序一样都属于比较排序中的一种,是通过比较数组中的元素来实现排序的,还给大家带来一种非比较排序计数排序,让我们开始今天的排序之吧!!!
|
5月前
|
搜索推荐 算法
【C/排序算法】:归并排序和计数排序
【C/排序算法】:归并排序和计数排序
40 0
|
6月前
|
存储 算法 前端开发
前端算法之计数排序
前端算法之计数排序
34 1
|
6月前
|
搜索推荐 C语言
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
40 0
|
6月前
|
存储 搜索推荐 算法
【数据结构】八大排序之计数排序算法
【数据结构】八大排序之计数排序算法
44 4
|
6月前
|
搜索推荐
排序算法--------计数排序
排序算法--------计数排序