基數(shù)排序是首先按最低有效位數(shù)字進(jìn)行排序，以解決卡片排序問題。
重復(fù)對(duì)所有的d位數(shù)字都進(jìn)行排序，僅需要d遍就可以將一堆卡片進(jìn)行排序。
這里又運(yùn)用了基數(shù)排序的方法，所以總的時(shí)間復(fù)雜度為O(n*d)。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cmath>
using namespace std;

void CountSort(int a[], int b[],int num,int d)   //計(jì)數(shù)排序
{
    int* c = new int[10];
    int index;
    for (int i=0;i<=9;i++)
       c[i]=0;
    int size = num;
    for (int j=0;j<size;j++)
    {
        index=a[j]%(int)pow(10.0,d)/(int)pow(10.0,d-1);
        c[index]++;
    }
    //c[i]包含等于i的元素個(gè)數(shù)
    for (i=1;i<=9;i++)
       c[i]=c[i]+c[i-1];
    //c[i]包含小于等于i的元素個(gè)數(shù)
    for (j=size-1;j>=0;j--)
    {
        index=a[j]%(int)pow(10.0,d)/(int)pow(10.0,d-1);
        b[c[index]-1]=a[j];
        c[index]--;
    }

    for (j=0;j<size;j++)    //更新一次排序后的a數(shù)組
    {
        a[j]=b[j];
    }
        delete [] c;
}

void RadixSort(int a[],int b[],int d,int num)   //基數(shù)排序
{
    for(int i=1;i<=d;i++)
        CountSort(a,b,num,i);
}


void main()
{
    int num,d;
    cout<<"輸入個(gè)數(shù)及位數(shù)"<<endl;
    cin>>num>>d;
    int* a = new int[num];
    int* b = new int[num];
    cout<<"排序前："<<endl;
    for(int i=0;i<num;i++)
    {
        cin>>a[i];
    }
        
    RadixSort(a,b,d,num);

    cout<<"排序后："<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<b[j]<<endl;
    }

    delete [] a;
    delete [] b;
}