猫史档案馆

也是好久没出新教程了，桶排序直到现在都还没讲。

其原因包括但不限于：外出旅游、学业问题、竞赛

总之反正不是因为懒

 

回忆一下我们接触过的排序：

冒泡、选择、插入等等

它们都有一个共同特点

就是交换

拿以前的例子举例：

[1,1,4,5,1,4]

选择排序的第一轮就是选出最小/大的数与当前最左边的交换

即

下标为1/4的数与下标为1/1的数交换

也就是最左边的1/5和最左边的1/最左边的1交换

今天要学习的计数排序与之前学习的有些许不同

它是依靠数组下标进行排序的（也就不进行交换就可以排序）

有点难懂，我们接下来来仔细认识一下

 

 

计数排序

假如有位小白兔叫芳芳

芳芳眼前有一笔直的地，上面每一个格子都种着一个萝卜

即[1,1,1,1,1,1,1……]

假如这块地只有10个萝卜

就是[1,1,1,1,1,1,1,1,1,1]

如果它把第1、4、5个萝卜拔掉了，然后让你统计还有哪些萝卜

你要怎么做

这也不是一个比较难的题

把拔掉的萝卜当作0，把还在的当作1

即[0,1,1,0,0,1,1,1,1,1]（注意数组最开头是以0为开头的,这里省略掉了第一个数）

再循环遍历，将数为1的数组下标输出

也就是2 3 6 7 8 9 10

 

那这和计数排序有什么关系呢？

注意，上面的例子输出的是数组下标，而计数排序也是一样的道理

计数排序是建立一个数组a[MAXN] （MAXN为大于等于1的任意整数）

将输入的数字x转换成数组a的数组下标然后自增

即a[x]++

随后顺序遍历数组

将指值非空的数的数组下标输出值非空的数次

打个比方

[1,1,4,5,1,4]

建立一个数组a[10]={0,0,0,0,0,0,0,0,0,0}（初始化只要一个{0}就行了，这里为了方便）

顺序输入

第一个数字是1

a[1]++

a={0,1,0,0,0,0,0,0,0,0}

第二个也是1

a[1]++

a={0,2,0,0,0,0,0,0,0,0}

第三个是4

a[4]++

a={0,2,0,0,1,0,0,0,0,0}

以此类推

最后

a={0,3,0,0,2,1,0,0,0,0}

然后顺序遍历

a[0]是空的，不输出

a[1]为3，输出三次1

a[2]是空的，不输出

a[3]是空的，不输出

a[4]为2，输出两次4

a[5]为1，输出一次5

a[6]是空的，不输出

……

a[9]是空的，不输出

这时输出栏：1 1 1 4 4 5

 

是不是很巧妙地运用了数组下标来解决问题？

计数排序的优点和缺点也很明显

优点是它基本上比每个需要交换的排序都要快

它的时间复杂度是O(n+k)（其中k是整数的范围，也可以理解为最大的值）

当然这是一种牺牲空间换取时间的做法

它的缺点很明显，如果里面有个贼大的数比如1145141919810

岂不是要开数组容量为1145141919810的数组？？？

以及当k比较大的时候，计数排序甚至不如O(n^2)的排序

它适合用于处理一些数比较小的排序

比如说：数学老师统计学生数学分数的情况

就可以用（初中这里数学满分100）（当然数学老师更喜欢用excel）

计数排序还有一个缺点是

他不能处理小数的排序（毕竟你数组下标不可能是小数）

总而言之，言而总之

它的优势在于在对一定范围内的整数排序时，快于任何比较排序算法。

 

 

 

好了，有关计数排序的内容我就讲到这里了

感兴趣的朋友可以去翻我之前的教学帖

也可以翻翻评论区看我有没有写代码）

再见awa

#include<iostream>
using namespace std;
const int MAXN=10001;
int a[MAXN],n;
int f[MAXN];
void counting(){
    for(int i=0;i<n;i++){
        f[a[i]]++;
    }
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<f[i];j++)
            cout<<i;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    counting();
    return 0;
}