苏炳添很快，计数排序也很快，比快速排序还快

作者：道哥

来源：经授权转自公众号 爱码有道（ID：aimayoudao）

大家好，我是道哥。高考的分数出来了，今天我们来聊聊与之相关的计数排序，而且在笔试面试中也经常碰到类似问题：

高考满分是750分，某省有n个考生，如何用尽可能低的时间复杂度来对所有考生的分数进行排序？

有的面试者看到这里，直接说用冒泡排序、选择排序、插入排序。显然，这是一个自掉身价的回答。

有的面试者回答说用快速排序、堆排序、归并排序。不错，快接近答案了，但依然不是最优的解法。

有的面试者被刷题所毒害，凡事不经思考，直接说这是海量数据问题，需要切割成小文件来处理。

其实，这哪里是什么海量数据问题呢？来看看本文要介绍的计数排序吧！其具体思路巧妙而又简单。

顾名思义，计数排序是通过计数来实现排序的，时间复杂度为O(n)，比快速排序还快，一起来看看。

图解计数排序

为了简便起见，我们假设在一次考试中有5个考生，满分是3分，很显然，这5个考生的分数值只可能是0，1，2，3，如下：

接下来，我们定义一个计数器，遍历上述每个考生，分别统计每个分数值有多少人：

所以，计数排序后的结果就是：

这便是计数排序的过程，时间复杂度为O(n)，整个过程中没有任何比较大小的操作，只有计数操作。

计数排序的思路看似简单，但很多面试者在现场是没法想到这种思路的，除非提前了解过计数排序。

计数排序代码

接下来，我们根据上述思路，来写一下计数排序的C++代码：

#include<iostream>
using namespace std;
 
void countSort(int a[], int n, int k)
{
  int *countArray = new int[k + 1]; 
  int *finalArray = new int[n]; 
 
  int i = 0;
  for(i = 0; i <= k; i++) 
  {
       countArray[i] = 0; 
  }

  for(i = 0; i < n; i++) 
  {
      countArray[a[i]]++;
  }

  for(i = 1; i <= k; i++) 
  {
       countArray[i] += countArray[i - 1];
  }

  for(i = 0; i < n; i++) 
  {
      finalArray[--countArray[a[i]]] = a[i]; 
  }
  
  for(i = 0; i < n; i++) 
  {
       a[i] = finalArray[i];
  }

  delete [] finalArray;
  delete [] countArray;
}
 
int main()
{
  int a[] = {2, 1, 2, 3, 0};
  int n = sizeof(a) / sizeof(a[0]);
  int maxPossibleScore = 3;
  countSort(a, n, maxPossibleScore);
  
  int i = 0;
  for(i = 0; i < n; i++)
  {
     cout << a[i] << " ";
  }
  
  cout << endl;
  return 0;
}

结果：0  1  2  2  3

也即：

计数排序，是常见的笔试面试内容，思路巧妙，大家都应该重视起来。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

你好，我是道哥，CSDN前30名，曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。

点分享

点点赞

点在看