计数排序实现基数排序

基数排序

简介

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

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

效率

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

数据结构	数组
最差时间复杂度	O(kN)
最差空间复杂度	O(kN)

以上内容整理自维基百科

实现

上述提到基数排序的原理是按位排序（必须是稳定的排序算法），对于位数不足的正整数要在高位补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;
}