第十二次上机报告

问题描述

基数排序算法设计，并测试

处理思路

基数排序主要用于对整数排序
对于k进制m位整数序列，可以用基数排序的方式来排序，其中不足m位的整数补足前导0
定义k个顺序队列，例如对于十进制整数排序，定义十个队列$q[0],q[1],...q[9]$
对于m位序列，执行m次排序，对于第i次排序
按照序列中从左到右的次序取数，若该数的第i位为t，则将该数入队列q[t]，将所有数按此方法入队。
然后再按照q[0]到q[k]的次序将整数逐步出队，存储回到原数组中，完成一次排序
重复k次即可

实际上是将全部整数从低位到高位逐步排序，最终完成整体排序。
深入一步说，对于要排序的元素定义了一个有限维线性空间，维度为整数的最大位数，所谓定义k个队列就是选取了线性空间的一组基。基内元素是线性无关的，这是k次排序互不相关的原因。
从这个角度上讲，基数排序可以扩展到有限位小数排序，位数增多而已。
对于抽象数据类型的排序，若是能定义对应的有限维空间，并选择对应的一组基，还能用某种方式（例如hash）转化成数据结构实现，那么基数排序应该也可以应用。
队列实现是为了保证基数排序的稳定性，放到同一个桶里的整数，先进先出，就以为着当前排序特征相同的元素，排序结束之后的次序和原次序一致。

代码设计

队列结构直接使用STL标准类queue

程序代码

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
#define N 50
queue<int>q[10];
int n,a[N];
int po10[11];
void init()
{
    po10[0] = 1;
    for(int i = 1; i <= 10; i++)
    {
        po10[i] = po10[i-1]*10;
    }
}
int getdig(int n)
{
    int dig = 0;
    while(n)
    {
        dig++;
        n/=10;
    }
    return dig;
}
int main()
{
    init();
    cout<<"Input amounts of numbers in the array.(at most 50 numbers)"<<endl;
    cin>>n;
    cout<<"Input "<<n<<" integers divided by a single space(at most 1e10): "<<endl;
    int dig = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
        dig = max(dig, getdig(a[i]));
    }
    for(int i = 1; i <= dig; i++)//i-th barrel-sort.
    {
        for(int j = 0; j < n; j++)
        {
            int now = a[j];
            int k = (int)(now / po10[i-1]) - 10 * (int)(now / po10[i]);
            if(k < 0 )k=0;
            q[k].push(now);
        }
        int index = 0;
        for(int j = 0; j < 10; j++)
        {
            while(!q[j].empty())
            {
                int now = q[j].front();
                q[j].pop();
                a[index++] = now;
            }
        }
        printf("******\n");
        printf("Barrel Sort #%d: \n",i);
        for(int k = 0; k < n; k++)
        {
            printf("%d ",a[k]);
        }
        printf("\n");
    }
    printf("The final result: \n");
    for(int i = 0; i < n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

测试效果

15个整数排序：将每次排序的结果也输出出来

Input amounts of numbers in the array.(at most 50 numbers)
15
Input 15 integers divided by a single space(at most 1e10):
23 122 033 0 1900 324353 877 254 5905 32 33 122 033 877 899
******
Barrel Sort #1:
0 1900 122 32 122 23 33 324353 33 33 254 5905 877 877 899
******
Barrel Sort #2:
0 1900 5905 122 122 23 32 33 33 33 324353 254 877 877 899
******
Barrel Sort #3:
0 23 32 33 33 33 122 122 254 324353 877 877 899 1900 5905
******
Barrel Sort #4:
0 23 32 33 33 33 122 122 254 877 877 899 1900 324353 5905
******
Barrel Sort #5:
0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353
******
Barrel Sort #6:
0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353
The final result:
0 23 32 33 33 33 122 122 254 877 877 899 1900 5905 324353