基数排序

排序思路

基数排序通过“分配”和收集过程来实现排序，不需要进行关键字的比较，是一种借助多关键字排序的思想对但关键字排序的方法。

基数排序分为两种：最低位优先（LSD）和最高为优先（MSD）。这里我们采用最低为优先，过程是：先按最低位的值对元素进行排序，在次基础上对次低位进行排序，依次类推，由低位向高位，每一趟都是根据关键字的一位并在上一趟的基础上对所有关键字进行排序，直至最高位。

注意：基数排序每一趟并不产生有序区，在最后一趟排序结束之前，所有元素并不一定归位。

通过基数排序对数列：{31，99，53，57，38，40，82，64，36，19}

 

排序算法

这里使用单链表来实现算法，其中结点类型RecType如下：

typedef struct node{

    char data[MAXD];//存放最大关键字的位数，是一个字符数组

    struct node * next;//指向下一个结点

}RecType;

基数排序算法如下

/**
参数p:为存储待排序序列的单链表的指针
参数r:为进制数。例如：2进制，10进制
参数d:为关键字位数
*/
void RadixSort(RecType *&p,int r,int d){
    //其中各链队的首尾指针，t用来在每次一刷选后将各链队按顺序连起来
    RecType *head[MAXR],*tail[MAXR],*t;
    int i,j,k;
    for(i=d-1;i>=0;i--){//筛选d趟：这里需要注意，因为待排序数据是反序存储的例如：31-》【3】【1】，高位对应低下标

        for(j=0;j<r;j++){//每一趟开始将各链队的首尾指针置为空
            head[j]=tail[j]=NULL;
        }

        while(p!=NULL){//循环原链表中的每个结点
            k=p->data[i]-'0';//第i趟筛选，将对应位置关键字转换成int 型

            if(head[k]==NULL){//k列链表第一次插入，将值插入head位置
                head[k]=p;
                tail[k]=p;
            }else{//第一次以后通过尾指针插入数据
                tail[k]->next=p;
                tail[k]=p;
            }
            p=p->next;//区下一个待排序指针
        }

        p=NULL;//重新用p来收集所有结点

        //将各个链表串在一起
        for(j=0;j<r;j++){
            if(head[j]!=NULL){
                if(p==NULL){
                    p=head[j];
                    t=tail[j];
                }else{
                    t->next=head[j];
                    t=tail[j];
                }
            }
        }

        t->next=NULL;//最后一个结点的next域置空
        cout<< (i==0?"个":"十") <<"\t";
        DispLink(p);//输出该趟排序结果

    }
}

为了能通过实例演示算法，这里需要添加两个函数：

建立单链表

/**
创建待排序单链表
参数L:用来存储待排序数列的指针，暂时是一个空的
参数a[][MAXD]:存放需要排序的数列的字符串
参数n:数列个数
*/
void Createlink(RecType *&L,char a[][MAXD],int n){
    int i,j;
    RecType * s,*r;//s用来每次存放数据，r尾指针
    L=r=NULL;//首先将头尾指针都置空
    for(i=0;i<n;i++){
        s=(RecType*)malloc(sizeof(RecType));
        for(j=0;j<MAXD;j++){
            s->data[j]=a[i][j];
        }
        if(L==NULL){//第一次将值赋给L
            L=s;
            r=L;
        }else{//第一次以后通过尾指针来添加
           r->next=s;
            r=s;
        }
    }
    r->next=NULL;//最后一个结点的next域置空
}

显示单链表

//显示数列
void DispLink(RecType *L){
    RecType * p=L;//指向开始结点
    while(p!=NULL){//遍历输出
        cout<<p->data<<",";
        p=p->next;
    }
    cout<<endl;
}

完整实例代码

#include <iostream>
#include <cstdlib>

using namespace std;

#define MAXD 2 //关键字位数
#define MAXR 10 //最大进制位数
typedef struct node{
    char data[MAXD];//存放关键字，是一个字符数组
    struct node * next;//指向下一个结点
}RecType;

/**
创建待排序单链表
参数L:用来存储待排序数列的指针，暂时是一个空的
参数a[][MAXD]:存放需要排序的数列的字符串
参数n:数列个数
*/
void Createlink(RecType *&L,char a[][MAXD],int n){
    int i,j;
    RecType * s,*r;//s用来每次存放数据，r尾指针
    L=r=NULL;//首先将头尾指针都置空
    for(i=0;i<n;i++){
        s=(RecType*)malloc(sizeof(RecType));
        for(j=0;j<MAXD;j++){
            s->data[j]=a[i][j];
        }
        if(L==NULL){//第一次将值赋给L
            L=s;
            r=L;
        }else{//第一次以后通过尾指针来添加
           r->next=s;
            r=s;
        }
    }
    r->next=NULL;//最后一个结点的next域置空
}


//显示数列
void DispLink(RecType *L){
    RecType * p=L;//指向开始结点
    while(p!=NULL){//遍历输出
        cout<<p->data<<",";
        p=p->next;
    }
    cout<<endl;
}

/**
参数p:为存储待排序序列的单链表的指针
参数r:为进制数。例如：2进制，10进制
参数d:为关键字位数
*/
void RadixSort(RecType *&p,int r,int d){
    //其中各链队的首尾指针，t用来在每次一刷选后将各链队按顺序连起来
    RecType *head[MAXR],*tail[MAXR],*t;
    int i,j,k;
    for(i=d-1;i>=0;i--){//筛选d趟：这里需要注意，因为待排序数据是反序存储的例如：31-》【3】【1】，高位对应低下标

        for(j=0;j<r;j++){//每一趟开始将各链队的首尾指针置为空
            head[j]=tail[j]=NULL;
        }

        while(p!=NULL){//循环原链表中的每个结点
            k=p->data[i]-'0';//第i趟筛选，将对应位置关键字转换成int 型

            if(head[k]==NULL){//k列链表第一次插入，将值插入head位置
                head[k]=p;
                tail[k]=p;
            }else{//第一次以后通过尾指针插入数据
                tail[k]->next=p;
                tail[k]=p;
            }
            p=p->next;//区下一个待排序指针
        }

        p=NULL;//重新用p来收集所有结点

        //将各个链表串在一起
        for(j=0;j<r;j++){
            if(head[j]!=NULL){
                if(p==NULL){
                    p=head[j];
                    t=tail[j];
                }else{
                    t->next=head[j];
                    t=tail[j];
                }
            }
        }

        t->next=NULL;//最后一个结点的next域置空
        cout<< (i==0?"个":"十") <<"\t";
        DispLink(p);//输出该趟排序结果

    }
}


int main()
{
    RecType *L;
    char a[10][2]={{'3','1'},{'9','9'},{'5','3'},
                {'5','7'},{'3','8'},{'4','0'},
                {'8','2'},{'6','4'},{'3','6'},
                {'1','9'}};

    //创建单链表
    Createlink(L,a,10);
    //基数排序
    RadixSort(L,10,2);
    return 0;
}

这里贴上数据结构书上的图例