计数排序&基数排序

在此之前我是不了解基数排序的， 昨天专门研究了下。 感觉是一种非常不错的排序算法。

时间复杂度很低o(n), 空间复杂度为o(n)。

说实话，没有多少种排序算法可以达到这样的性能。

仔细研究了下，发现在很多种情况下采用这样算法可以做到很好的处理。 （例如字符串排序， 电话号码排序等）

一、计数排序

如果想要学会基数排序， 那么首先要了解计数排序， 因为基数排序封装了计数排序。

那么对于计数排序， 我有一种很强烈的感觉就是用空间换取时间。

我想大家都知道哈希思想。

1、开辟一块很大的辅助空间（能够存储最大值）， 辅助空间中的下标对应元素本身， 2、下标对应的值是该元素出现的个数。 3、最后遍历辅助空间， 累计出现的次数然后存储起来就排序成功。

非常推荐大家看这篇文章： 计数排序

Code

//版本一 vector<int> CountSort(int* arr, int len) { if (!arr || len <= 0) { return vector<int>(); } int max = arr[0]; //使得max获取最大值 for (int i = 1; i < len; i++) { if (max < arr[i]) { max = arr[i]; } } //创建辅助数组 vector<int> tmp_arr(max + 1, 0); //累次出现次数 for (int i = 0; i < len; i++) { tmp_arr[arr[i]]++; } //遍历辅助数组， 存储在ret_arr中返回 vector<int> ret_arr(len); int index = 0; for (int i = 0; i < tmp_arr.size(); i++) { while (tmp_arr[i]) { ret_arr[index++] = i; tmp_arr[i]--; //计数器-- } } return ret_arr; }

这个算法我们可以发现

1、首先获取序列中的max值。 时间复杂度为o(n) 2、开辟辅助数组空间， 空间复杂度为s(max) 3、最后遍历辅助数组， 时间复杂度为o(max), 4、还开辟了s(n)的数组， 存储遍历后有序的序列。 综上所述：时间复杂度：o(n+max)； 空间复杂度：s(max+n)

我们可以发现优化核心是max值， 如果序列中只有5个元素， 但是有一个值很大， 我们都会开辟max大数组空间， 空间利用率很低。 [100, 102, 105, 107, 110] 最大值为110， 开辟从0到110大小空间。

优化一

//版本二 vector<int> CountSort1(int* arr, int len) { if (!arr || len <= 0) { return vector<int>(); } int min = arr[0], max = arr[0]; //1、获取最大值和最小值 for (int i = 0; i < len; i++) { if (max < arr[i]) { max = arr[i]; } if (min > arr[i]) { min = arr[i]; } } //2、开辟辅助空间 - 统计次数 vector<int> tmp_arr(max - min + 1, 0); for (int i = 0; i < len; i++) { tmp_arr[arr[i] - min]++; } //3、遍历辅助空间， 获取有序序列 vector<int> ret_arr(len, 0); int index = 0; for (int i = 0; i < tmp_arr.size(); i++) { while (tmp_arr[i]) { ret_arr[index++] = i + min; tmp_arr[i]--; } } return ret_arr; }

对于刚才上述的问题， 我们获取最大值max和最小值min， 开辟max-min+1的空间开销。

[100, 102, 105, 107, 110] 我们只需要开辟10个大小空间就可以， 空间利用率明显提升。

我们可以发现这种计数排序并不是真正意义上的排序， 只是统计次数而已。当遇到重复时， 无法保证稳定性。

优化二

vector<int> CountSort3(int* arr, int len) { if (!arr || len <= 0) { return vector<int>(); } int min = arr[0], max = arr[0]; //1、获取最大最小值 for (int i = 0; i < len; i++) { if (max < arr[i]) { max = arr[i]; } if (min > arr[i]) { min = arr[i]; } } vector<int> tmp_arr(max - min + 1, 0); //开辟存储数组 //2、确定对应的个数 for (int i = 0; i < len; i++) { tmp_arr[arr[i] - min]++; } //3、统计数组变形，后面的元素等于前面元素次数之和 int sum = 0; for (int i = 0; i < tmp_arr.size(); i++) { sum += tmp_arr[i]; tmp_arr[i] = sum; } //4、倒叙遍历原始数组， 从统计数组中找到正确位置，输出到结果数组 vector<int> ret_arr(len); for (int i = len-1; i >= 0; i--) { ret_arr[tmp_arr[arr[i] -min] - 1] = arr[i]; tmp_arr[arr[i] - min]--; } return ret_arr; }

优化后的计数排序是稳定排序！

综上所述: 1、计数排序存在第一个问题， min和max相差很大会导致开辟的空间很大， 如果数组大小很小可能会导致空间利用率很低。 2、第二个问题，只能处理整型值。

优点: 时间复杂度很好o(n)。

二、基数排序

基数排序可以很有效解决计数排序存在的问题， 为什么呢？

非常建议大家阅读下这位大佬的文章： 基数排序

这篇文章给了两种类型排序： 一种是字符串排序，另一种是电话号码排序。

大体思想：

我们都知道字符串分为很多个字符组成，我们每一次对一位字符进行一次计数排序。 保存计数排序后的序列， 然后下一位进行一次计数排序。 最终把所有位处理完毕。 （由于这篇文章已经把所有情况说明完毕， 我在这里作为性能分析！）

#include <iostream> #include <vector> #include <string> using namespace std; int GetCharIndex(string str, int k) { //k为第几位 0， 1， 2 if (str.size() < k) { //不存在这一位， 相当于补0 return 0; } int index = str.size() - 1; while (k) { k--; index--; } return str[index]; //返回的字符 } vector<string> RadixSort(vector<string> str, int len, int maxlen) { if (str.empty()) { return vector<string>(); } //从个位开始 - 从低位到高位 for (int k = 0; k < maxlen; k++) { //1、计数排序共分为3步 //创建辅助排序数组， 对应入座 //由于是字符，这块我采用128， 所有可能的情况 vector<int> tmp_arr(128, 0); for (int i = 0; i < len; i++) { int index = GetCharIndex(str[i], k); //获取对应的字符 - 采用ASCII tmp_arr[index]++; } //2、统计数组变形，后面的元素等于前面元素次数之和 for (int i = 1; i < tmp_arr.size(); i++) { tmp_arr[i] = tmp_arr[i] + tmp_arr[i - 1]; } //3、倒叙遍历原始数组， 从统计数组中找到正确位置，输出到结果数组 vector<string> ret_arr(len); for (int i = len - 1; i >= 0; i--) { int index = GetCharIndex(str[i], k); ret_arr[tmp_arr[index] - 1] = str[i]; tmp_arr[index]--; } str = ret_arr; //赋值 } return str; } //获取所有字符串中最大长度 int GetMaxLen(vector<string> str, int len) { int maxlen = str[0].size(); for (int i = 1; i < len; i++) { if (str[i].size() > maxlen) { maxlen = str[i].size(); } } return maxlen; } int main() { vector<string> str{ "bda", "cfd", "qwe", "yui", "abc", "rrr", "uue" }; int maxlen = GetMaxLen(str, str.size()); vector<string> vec = RadixSort(str, str.size(), maxlen); for (auto& it : vec) { cout << it << ' '; } cout << endl; }

基于上述的基数排序， 我们来看看是否能解决计数排序存在的问题。

第一点就是空间利用率很差的问题， 由于是对每一位进行操作，对于上述中也就是小写字母字符， 我们完全可以开辟固定大小的辅助空间处理。上述为了解决问题采用128所有字符的情况作为辅助数组。 我们可以发现是固定的长度-解决了计数排序存在的问题。

第二点是可以处理字符串类型。 而且还有点匹配， 很好处理。

分析性能： 时间复杂度o(maxlen * n)， 这个maxlen可以近似为常量。 是非常不错的性能。

电话号码排序：

基于字符串排序的思想， 我们也可以解决电话号码排序的问题， 为了方便操作， 我这块采用的是字符串存储电话号码。

#include <iostream> #include <string> #include <vector> using namespace std; int GetCharIndex(string str, int k) { //由于是手机号，固定的长度， 因此不会出现偏差 if (k > str.size()) { return 0; } int index = str.size() - 1; while (k) { k--; index--; } return str[index] - '0'; } vector<string> RadixSort(vector<string> strarr, int maxlen) { if (strarr.empty() || maxlen <= 0) { return vector<string>(); } for (int k = 0; k < maxlen; k++) { //1、计数排序 - 第一步： 开辟额外数组 vector<int> count_arr(10, 0); //由于每一位是0~9， 因此开辟10即可 for (int i = 0; i < strarr.size(); i++) { int index = GetCharIndex(strarr[i], k); count_arr[index]++; } //2、统计数组变形 for (int i = 1; i < count_arr.size(); i++) { count_arr[i] = count_arr[i] + count_arr[i - 1]; } //3、倒序遍历数组 vector<string> ret_arr(strarr.size()); for (int i = strarr.size() - 1; i >= 0; i--) { int index = GetCharIndex(strarr[i], k); ret_arr[count_arr[index] - 1] = strarr[i]; count_arr[index]--; } strarr = ret_arr; } return strarr; } int main() { vector<string> str{ "18914021920", "13223132981", "13566632981", "13660891039", "13361323035" }; int maxlen = str[0].size(); vector<string> vec = RadixSort(str, maxlen); for (const auto& it : vec) { cout << it << ' '; } cout << endl; return 0; }

可以发现对于每一位来说， 也就是0~9的可能性， 辅助数组只需要10大小的空间。 可以看作是个常量。 非常不错， 性能也非常好。

关键有个很大的优点： 可以解决大数问题。我们使用字符串存储值， 不存在超过int范围的问题。 每一次也是对一位进行操作进行计数排序。 因此是可以处理大数问题的排序的。

测试用例:

#include <iostream> #include <string> #include <vector> using namespace std; int GetCharIndex(string str, int k) { //由于是手机号，固定的长度， 因此不会出现偏差 if (k > str.size()) { return 0; } int index = str.size() - 1; while (k) { k--; index--; } return str[index] - '0'; } vector<string> RadixSort(vector<string> strarr, int maxlen) { if (strarr.empty() || maxlen <= 0) { return vector<string>(); } for (int k = 0; k < maxlen; k++) { //1、计数排序 - 第一步： 开辟额外数组 vector<int> count_arr(10, 0); //由于每一位是0~9， 因此开辟10即可 for (int i = 0; i < strarr.size(); i++) { int index = GetCharIndex(strarr[i], k); count_arr[index]++; } //2、统计数组变形 for (int i = 1; i < count_arr.size(); i++) { count_arr[i] = count_arr[i] + count_arr[i - 1]; } //3、倒序遍历数组 vector<string> ret_arr(strarr.size()); for (int i = strarr.size() - 1; i >= 0; i--) { int index = GetCharIndex(strarr[i], k); ret_arr[count_arr[index] - 1] = strarr[i]; count_arr[index]--; } strarr = ret_arr; } return strarr; } int main() { vector<string> str{ "18914021920111111111111111111117777777777777777", "13223132981111111111111111111117777777777777777", "13566632981111111111111111111117777777777777777", "13660891039111111111111111111117777777777777777", "13361323035111111111111111111117777777777777777" }; int maxlen = str[0].size(); vector<string> vec = RadixSort(str, maxlen); for (const auto& it : vec) { cout << it << ' '; } cout << endl; return 0; }

测试结果：