计数排序实现基数排序

分手后的思念是犯贱 2022-07-28 11:41 268阅读 0赞

# 基数排序 #

## 简介 ##

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

## 效率 ##

基数排序的时间复杂度是O(k⋅n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n⋅log(n))，k的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。

<table> 
 <thead> 
 <tr> 
 <th>数据结构</th> 
 <th>数组</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>最差时间复杂度</td> 
 <td> O(kN) </td> 
 </tr> 
 <tr> 
 <td>最差空间复杂度</td> 
 <td> O(kN) </td> 
 </tr> 
 </tbody> 
</table>

以上内容整理自[维基百科][Link 1]

--------------------

## 实现 ##

上述提到基数排序的原理是按位排序（必须是稳定的排序算法），对于位数不足的正整数要在高位补0，根据此，得出伪代码：

RADIX-SORT(A,d)
        for i: 1 to d
            do use a stable sort to sort array A on digit i

这里的稳定排序可以是计数排序和桶排序（中文维基上给的示例是桶排序），这里我用**`计数排序`**来实现它。  
由于基数排序适用于正整数、字符串、特定格式的浮点数排序，这里不方便写成模板的方式（或者是我能力还不够LOL），我就写了正整数的排序版本。

### **代码** ###

#ifndef MYSORT_H_
 #define MYSORT_H_
 #include <iostream>
 #include <limits>
 namespace MySort{
 template <typename T>
 void Counting_Sort(T *data,T*A, T*B, int k, size_t n)//修改的计数排序
 {
 //n= length(A)
 T *C = new T[k + 1];
 for (int i = 0; i <= k; i++)
 {
 *(C + i) = 0;
 }//初始化辅助空间C
 for (int i = 0; i < n; i++)
 {
 *(C + *(A + i)) = *(C + *(A + i)) + 1;
 }//计数
 for (int i = 1; i <= k; i++)
 {
 *(C + i) = *(C + i) + *(C + i - 1);
 }
 
 for (int i = n - 1; i >= 0; i--)
 {
 *(B + *(C + *(A + i)) - 1) = *(data + i);//把data[i]放在其前面数总和的下一个位置
 *(C + *(A + i)) = *(C + *(A + i)) - 1;//排除存在相同元素的情况
 }
 
 delete[]C;
 }
 
 
 int max_bits(int a[],int n)//求最大位数
 {
 int maxNum=a[0];
 for (int i = 0; i < n; i++)
 {
 if (maxNum < a[i])
 {
 maxNum = a[i];
 }
 }
 int bit = 0;
 while (maxNum)
 {
 maxNum /= 10;
 bit++;
 }
 return bit;
 }
 int genBit(int value, int i)
 {
 return (value / (int)pow(10, i - 1)) % 10;
 }
 void Radix_Sort(int a[], int n,int k)
 {
 int *src = new int[n];
 //a[]表示待比较的数
 //n表示待比较元素的个数
 //k表示待比较元素中长度最长的长度
 //int k = max_bits(a, n);
 for (int i = 1; i <= k; i++)
 {
 int* dest = new int[n];
 for (int j = 0; j < n; j++)
 {
 src[j] = genBit(a[j], i);//tmp成为计数排序中待比较的值
 }
 Counting_Sort<int>(a,src, dest, 10, n);//重载版本
 for (int k = 0; k < n; k++)
 {
 a[k] = dest[k];
 }
 delete[]dest;
 }
 delete[] src;
 }
 }//namespace MySort
 #endif

测试代码

#include <iostream>
 #include "MySort.h"
 using namespace std;
 int main()
 {
 
 int a[] = { 234, 114, 5, 44, 3231, 98 };
 int aSize = sizeof(a) / sizeof(int);
 int maxBits = MySort::max_bits(a, aSize);
 MySort::Radix_Sort(a, aSize, maxBits);
 for (int i = 0; i < aSize; i++)
 {
 cout << a[i] << endl;
 }
 
 system("PAUSE");
 return 0;
 }

[Link 1]: https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F