CSP-J/S常考算法探秘:不用比较也能排序(1)——基数排序

算法探秘：不用比较也能排序（1）

——基数排序

排序算法是通过特定的算法将一组或多组数据按照一定的模式进行排序，通常为从小到大或从大到小或按字典序排列。

在洛谷中有这样一道排序的模板题：

如果使用经典的排序方法，例如冒泡排序、选择排序、插入排序等，由于时间复杂度在O(n^2)，对于10000个数字而言，需要进行的操作最多高达1亿次，程序进行这些操作的时间大概为1秒钟。

但是题目要求程序要在1秒内完成5个测试点，显然这些排序算法满足不了高效排序的要求。

此时有同学学过快速排序（或者直接调用sort()函数）、堆排序、归并排序等，可以将排序的时间复杂度降低到O(nlogn)，轻松通过该题。

（图为快速排序的测试结果）

那么，有没有效率更高的排序呢？以上这些排序都是基于数据比较的排序，只要涉及到比较就需要两两对比，就必定包含一个外循环是遍历整个数组的双重循环，时间复杂度的下限就只能在O(nlogn)上。

除了基于比较的排序外，还有三种不需要比较也能排序的排序算法——计数排序、基数排序和桶排序，它们的原理是利用了数组下标是有序的特点，属于线性排序算法，时间复杂度都为O(n+k)（其中，n为数组元素个数，k为对元素进行分组的组数）。

本期，将带着大家学习第一种线性排序算法——基数排序。

基数排序的基本思想

基数排序的基本思想是对于待排序的序列按数字的数位进行多趟排序，先按照低位排序，然后收集结果；再按照高位排序、收集结果；以此类推，直到按照了最高位进行排序，最后收集的结果就是排序完成的结果。

这种思想能够实现排序的基本原理大致可以这么描述：对于两个十进制数来说，位数多的那个数字更大；位数一样的话，高位大的数字更大。因此，在两个数的比较过程中，高位比较的优先级最大，低位比较的优先级最低。

例如123、82、39三个数字,只有123有百位，肯定最大，在82和39中，十位上8>3，因此82>39。

基数排序的过程

（1）先输入所有待排序的数字，并找到序列中的最大值，取得最多的位数；

例如上面待排序的序列中，最大值为616，是个三位数，因此接下来要按照个位、十位、百位的顺序进行3趟排序；

（2）按个位进行排序，将个位相同的元素放入同一个“桶”中。（此处的“桶”相当于一个容器，用来存放数位相同的元素）

对于上述序列，设计了10个“桶”，分别存放个位是0~9的数字，在代码中可以定义一个大小为10的数组a当做“桶”。

（3）按照“先进先出”的原则，按“桶”的顺序依次取出元素，排成一排。上述序列第一次排序后的结果如下：

（4）以第一次排序的结果为基准，对十位数进行排序，如果没有十位数（例如“2”），则在十位上用0补全。同样地，十位相同的元素放入同一个“桶”中。分配结果如下：

此处为了便于理解，在“2”和“8”的前面都补全了0，实际算法运行过程中是没有0的。

（5）再次按“先进先出”的原则将数据排成一排：

可以看到，如果去掉所有的三位数，剩下的一位数和二位数已经是有序的了。

（6）以第二次排序的结果为基准，再次对百位进行“桶”分配，没有百位的数字在百位上用0补全。

（6）再重新将数据排成一排：

数列已经变成一个有序序列了。

基数排序的时空复杂度分析

以上面的序列为例，总共进行了3次与数位相关的排序，每次排序都是将所有数字先分配到对应的10个“桶”中，再从“桶”取出来，再将中间结果返回到原数组中，因此基数排序的时间复杂度为O(d(n+k)) = T(d(3n+k))，其中d为最大值的位数，n为数组元素个数，k为“桶”的个数。

如果最大值的位数远小于序列元素个数，那么时间复杂度可以近似地看作是O(n+k)。

在算法过程中，需要分配的空间有：原数组空间、“桶”的空间、存放中间过程结果的空间，因此空间复杂度也为O(n+k)。

基数排序的优势

（1）对于拥有正整数或整数编码的字符串来说，线性排序算法的时间复杂度低，效率极高；

（2）在排序过程中，能够保证相等元素的原始相对顺序，排序算法稳定；

（3）不仅是基数排序，计数排序和桶排序都是用空间换时间的排序算法，在现在内存都很大的时代，其空间复杂度仍旧不算高，因此在处理大规模数据时也能有出色的表现。

但是，基数排序对于数据有一定的限制，如果遇到浮点数、复杂对象等数据类型，需要将数据进行预处理后才能排序。

代码展示：

#include<iostream>
#include<cstring> 
#include<ctime>
using namespace std;
#define N 20 //以20个元素的数组为例 
int a[N]; 
int main(){
  srand(time(0));//设置随机数种子
  cout<<"排序前："; 
  for(int i=0;i<N;i++){
    a[i]=rand()%1000;//随机生成20个1000以内的数字 
    cout<<a[i]<<" "; //初始化待排序的数组并展示 
  }
  cout<<endl;
  //下面开始基数排序
  int maxx=0;
  for(int i=0;i<N;i++){
    maxx=max(maxx,a[i]);
  }
  int d=0;
  while(maxx){
    maxx/=10;
    d++;
  }//计算出最大值的位数d
  int base=1; //从个位开始排序
  int cnt[10]; //设置好0~9十个桶 
  int tmp[N]; //临时数组存放每趟排序的结果 
  for(int i=0;i<d;i++){
    memset(cnt,0,sizeof(cnt));//初始化各个桶为空 
    for(int j=0;j<N;j++){
      cnt[a[j]/base%10]++; 
      //分别统计当前趟数位中各数（例如个位的0~9）的数量 
    }
    for(int j=1;j<10;j++){
      cnt[j]+=cnt[j-1];
      //记录每个数位最后的位置（例如cnt[2]=5表示按个位排序后，个位是2的最后一个数字在位置5上） 
    }
    for(int j=N-1;j>=0;j--){
      //从后往前，将每个数字按当前趟的数位（例如个位）最后的位置放数字进tmp数组 
      tmp[cnt[a[j]/base%10]-1]=a[j]; 
      cnt[a[j]/base%10]--; //放好一个数字（例如个位是2的数字）后，位置往前1个 
    } 
    cout<<"第"<<i+1<<"次排序结果："; 
    for(int j=0;j<N;j++){
      a[j]=tmp[j]; //将第i轮排序结果更新回原数组 
      cout<<a[j]<<" ";
    }
    cout<<endl;
    base*=10;//准备下一个数位的排序 
  }
  return 0; 
}

运行结果

课后同学们可以根据老师给出的算法思路与代码展示，使用基数排序的技巧来完成洛谷上“P1177 【模板】排序”这一题，记录程序AC后的用时与内存消耗，与前面的快速排序对比，理解线性排序算法用空间换时间的特点。