文章目录
- 什么是基数排序
- 稳定的计数排序
- 基数排序的实现
- 复杂度
数据结构与算法 | 计数排序
在之前的博客中，我介绍过一种非比较排序——计数排序。
计数排序的原理很简单，就是用一个数组来统计每种数字出现的次数，然后按照大小顺序将其依次放回原数组，达成排序的目的。
但是计数排序有一个很严重的问题，就是其只能对整数进行排序，一旦遇到字符串时，就无能为力了。
为了弥补上述的缺点，针对于字符串的基数排序诞生了。
基数排序在计数排序的基础上进行了改进，将排序工作拆分为多个阶段，每一个阶段只根据一个字符进行排序，一共排序k轮(k为数据长度)
例如我们需要对一组三个英文字母组成的字符串进行排序，按照以上规则，进行三轮排序。
（ps:这里用的lsd法）我们从低位往高位开始排，按照计数排序的思想，统计所有出现过的字符，按照其在ascii表中的顺序依次排序，得到以下结果
此时在第一轮的基础上，对倒数第二个字符进行排序
在第二轮的基础上，再对第一个字符进行排序
如此一来，就得到了有序的序列。这种将字符串拆分为多位，每位进行计数排序的算法，就是基数排序。
从上面来看，每一位的排序都基于上一位的基础，所以这也就要求我们的计数排序必须是稳定的，否则前后顺序无法保证，多轮的排序就没有了意义，下面就介绍如何实现稳定的计数排序。
在之前的博客中，我当时介绍的计数排序是不稳定的，下面就对其进行改造，将其变为稳定排序。
那要这么做呢？我们知道，计数排序中的统计数组中存储了每个数字出现的次数，而我们还原时也只是按照数字来依次将其放回，这也就是其不稳定的原因，因为统计数组丝毫没有关心其在原数组中的位置。
要改进这一点，可以通过以下方法来实现，只需要加上几行简单的代码即可。
//保证计数排序稳定，对数组变形，统计数组的每一个位置的值为前面所有数字的数量合
//变形后每个位置的值即为该数据的排序的序号
int sum = 0;
for(int i = 0; i < range; i )
{
sum = count[i];
count[i] = sum;
}
如上面代码，我们需要让统计数组中不再记录数组出现的次数，而是记录该位置前面所有数字出现的次数和，这种方式能让我们巧妙地得到序号。
例如下图
这样做的目的是什么呢？
//按照原数组的数据的位置，倒序将数据放回原位，确保稳定性
vector temp(arr.size(), 0);
for(int i = arr.size() - 1; i >= 0; i--)
{
//序号-1才是下标位置
temp[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
因为我们此时统计数组中每一个位置的值，变成了由数组开头到那个位置所有元素的和，这也就意味着，他此时变成了一个排名。
例如在原数据中有两个93，一个在前，一个在后，并且统计数组中93的位置为7。
我们通过上述方法，从后往前遍历时，将后面的93放到第七个位置，接着统计数组对应位置的排名减一，此时当我们放入前面的93时，他就变成了第六位，这样就保证了其稳定性。
这个看代码更好理解，思路都写在了注释中，改造完后的计数排序代码如下。
void countsort(vector& arr)
{
int max = arr[0], min = arr[0];
//找出最大值和最小值，缩减范围
for(int i = 1; i < arr.size(); i )
{
if(arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
int range = max - min 1;
vector count(range, 0); //统计数组
//统计每种数字出现的次数
for(int i = 0; i < arr.size(); i )
{
count[arr[i] - min] ;
}
//保证计数排序稳定，对数组变形，统计数组的每一个位置的值为前面所有数字的数量合
//变形后每个位置的值即为该数据的排序的序号
int sum = 0;
for(int i = 0; i < range; i )
{
sum = count[i];
count[i] = sum;
}
//按照原数组的数据的位置，倒序将数据放回原位，确保稳定性
vector temp(arr.size(), 0);
for(int i = arr.size() - 1; i >= 0; i--)
{
//序号-1才是下标位置
temp[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
arr = temp; //将临时数据拷贝回原数组
}
在写基数排序之前，还有一个小问题需要说明一下，由于前面我们所说的情况都是字符串长度相等的时候，如果字符串长度不相同时，怎么处理呢？
因为字符串并不像整数一样排序依赖于长度，其排序主要依赖于字典序，所以我们以字符串中最长的数据为标准，而长度不足的在尾部补零即可。
实现代码如下
int getindex(const string& str, int index)
{
//如果超出字符串长度，则补零
if(index >= str.size())
{
return 0;
}
return str[index];
}
void radixsort(vector& arr, int maxlen)
{
vector temp(arr); //临时数组，用来保留每一趟的结果
//从字符串尾部的字符依次向前排序
for(int i = maxlen - 1; i >= 0; i--)
{
vector count(128, 0); //统计数组，这里图方便直接给了ascii的前128个
//统计每种数字出现的次数
for(int j = 0; j < arr.size(); j )
{
int index = getindex(arr[j], i);
count[index] ;
}
//保证计数排序稳定，对数组变形，统计数组的每一个位置的值为前面所有数字的数量合
//变形后每个位置的值即为该数据的排序的序号
int sum = 0;
for(int j = 0; j < count.size(); j )
{
sum = count[j];
count[j] = sum;
}
//按照原数组的数据的位置，倒序将数据放回原位，确保稳定性
for(int j = arr.size() - 1; j >= 0; j--)
{
int index = getindex(arr[j], i);
temp[count[index] - 1] = arr[j];
count[index]--;
}
arr = temp; //将临时数据拷贝回原数组，因为下一轮需要借助上一轮的顺序继续排序
}
}
- 时间复杂度：o(k * (n m))，n为数据数量，m为字符取值范围，k为执行的计数排序次数。
- 空间复杂度：o(n m)， n为数据数量，m为字符取值范围