vlambda博客
学习文章列表

鸽了这么长时间，突然意识到我有必要刷一下存在感。

因为作者被数据结构带作业恶心坏了，天天净编程，所以本次推送是关于算法的，该算法是我大作业的核心算法之一。

没有接触过编程的同学可能没办法体会该篇推送内容的绝妙之处与魅力所在，在此表示抱歉。

现在，进入正题。

第一章 -> 基础信息介绍

名称：计数排序

时间复杂度：O(n+k)   //线性时间！k是数组中最大值与最小值的差

空间复杂度：O(n+k)   //O(n+2k)

稳定性：稳定

适用范围：整型及其他可以转换为整型比较的数据

适合场合：数组元素的最小值和最大值相差不大

基于比较：否

实现难度：尚可

细心的同学可能注意到了，计数排序的时间复杂度是线性的O(n+k)，那是因为，计数排序不比较数组元素之间的大小。

根据斯特林公式，任何基于比较的排序，平均时间复杂度都不会低于O(nlogn)。通过计算可得出，n一定时，当k小于某个值时，该算法的速度将会高于任何基于比较的排序！

要知道，冒泡排序，选择排序等简单排序算法的时间复杂度是O(n*n)，即使是更快一些的归并排序、快速排序和希尔排序，时间复杂度也无法达到线性！

当排序数量越来越大时，它们的运行时间将会更快地增长（导数与n正相关），而线性的时间能够保证计数排序无论数量多少都可以高效地完成任务！（含有夸张成分）

简要介绍便到此为止。我们开始介绍计数排序的原理。

第二章 -> 原理介绍

大家有遇到过和自己同一天生日的同学或者朋友嘛？你是否好奇过，一个班里出现同一天生日的同学的概率有多大？

N个人中，一定有2人同一天生日，那么N至少多大呢？请读者思考这个问题。

答案是367，如果不考虑闰年，就是366，等于一年的天数加一。

这个问题的原理叫做“抽屉原理”（又名鸽巢原理，感兴趣的同学可以搜索鸽巢排序），由狄利克雷首先提出。

无论如何放置，N个抽屉至少有一个放了两个物品，那么物品数至少为N+1。除了这个结论以外，抽屉原理还有关于无限的有趣结论，感兴趣的同学可以搜索。

就像这样。

计数排序的原理便是造一个辅助数组作为“抽屉”。

下面进入正式讲解。

第三章 -> 算法讲解

需要排序的数组设为arr。arr[13] = {1,1,4,5,1,4,1,9,1,9,8,1,0}。

首先找到arr中最小的数字，是0。再找出最大值，是9。那么我们将变量max赋值为9，min赋值为0。

然后，我们需要建立两个辅助数组tmp1和tmp2，即“抽屉”。数组大小等于max – min + 1。

为什么是这个大小呢？tmp1[i]存储的是“arr中值为i + min的元素的个数”，因此我们会将元素放入tmp1中角标等于元素值减最小值的位置。这样当然可能出现空抽屉，原数组里不存在等于该值的元素呗。

将所有元素依次放入tmp1的“与其值对应的”位置（即角标等于arr[i] – min），每放入一个便将tmp1对应位置的值加一（即统计arr中相同数的数量，共有2个4，那么tmp1[4 – 0]的最终值便是2。

全部放完以后，我们再对tmp2进行操作。tmp2[i]存储的是“arr中小于等于i + min的元素个数”。比如，tmp2[0 - 0] = 1，tmp2[1 - 0] = 7……

我们只需要遍历一遍tmp1就可以求出tmp2中所有的值。

如果你已经弄明白发生了什么，这里有个提示帮助你理解：tmp2的最后一个元素一定等于arr的大小，即13。

为什么要做tmp2呢？

我们反向遍历原数组arr，此时，arr[i]在返回数组中的位置我们就可以通过tmp2找到了。

tmp2角标等于arr[i] - min的位置存放什么呢？当然是小于等于arr[i]的元素个数（由此思考为何反向遍历）！那么我们直接可以确定arr[i]应该排第几了。这里做一个比喻，比如一场考试，你知道你前面，加上你自己有50个人，那你就是第50名（假设没有和你分数相同的）。

但不要忘了，和排名不同，数组编号从0开始。因此第13个数应该在编号12的位置。所以在放置之前要对tmp2相应位置的值减一。

本图放入的是原数据，当然改成其他的也可以哦，比如返回原数组按值排好序的编号……

这样，返回数组的这个元素位置便确定了。这个位置等于……tmp2中arr[i] - min位置存放的值减一（好复杂）。当然，我们在放入每个元素前都对tmp2[arr[i] – min]减一也起到了保证后面和arr[i]相同的元素不会和前面的元素发生位置冲突（即占据同一个位置），防止新放入的数据覆盖前一个数据的作用。

遍历完成，所有元素便完成了排序！提示，不被《Re:从零开始的C语言数组编号》搞晕就算成功。

示例代码

//再快的算法也拯救不了你的灵魂。//不要往代码里加意义不明的注释！//counting函数返回的是从小到大排序的编号而非数值。#include <stdio.h>#include <stdlib.h>int* counting(int*, int);void main(){ int n = 10,i; int* arr = (int*)malloc(sizeof(int) * n); int* ret; for (i = 0; i < n; ++i) arr[i] = rand();  ret = counting(arr,n); for (i = 0; i < n; ++i) printf("%d : %d\n", ret[i],arr[ret[i]]);
}int* counting(int* arr, int size){ int max = arr[0], min = arr[0], i; int* retArr = (int*)malloc(sizeof(int) * size); for (i = 0; i < size; ++i) { if (arr[i] > max) max = arr[i]; else if (arr[i] < min) min = arr[i]; } int* tmp1 = (int*)malloc(sizeof(int) * (max - min + 1)); int* tmp2 = (int*)malloc(sizeof(int) * (max - min + 1)); for (i = 0; i <= max - min; ++i) tmp1[i] = 0; for (i = 0; i < size; ++i) ++tmp1[arr[i] - min]; tmp2[0] = tmp1[0]; for (i = 1; i <= max - min; ++i) tmp2[i] = tmp1[i] + tmp2[i - 1]; for (i = size - 1; i >= 0; --i) retArr[--tmp2[arr[i] - min]] = i; free(tmp1); free(tmp2); return retArr;}//2021, Amo Inko. All Rights Reserved.

写在最后 != NULL

该算法并非本人原创，且在CSDN中已有很多讲解。本人亦是通过CSDN学习后写出本代码。本文仅作科普用途，存在重复和雷同是必然现象，还请谅解。有错误请指正。

信任是合作的基石，我们鼓励共赢，抵制投机取巧。代码仅作参考，若copy代码直接提交导致查重不过关等严重问题，违规读者方负全部责任，特此声明！

如果看了还不懂，可以匿名向我提问，提问箱二维码如下，长按识别。（如果弄清位置和值的关系，问题就迎刃而解啦）

悄悄说，即便你把我的示例代码直接复制上去，也会得到令人激动的WA哦。要满足题意，需要对代码进行小小的修改。但我再次强调，建议独立实现该算法！（虽然写出来都一个样儿）

另：注释署名Amo Inko是我的笔名，虽然没写真名，但所有权仍归我哦。