#ifndef LINKEDLISTSORT_H
#define LINKEDLISTSORT_H

#include<iostream.h>
#include<stdlib.h>
const int DefaultSize=50;
const int maxValue=10000;

//////////////////////////////////////////////////
//ListNode<T>链表结点结构的定义
//T是数据域的类型
//////////////////////////////////////////////////
template<class T>
struct ListNode
{
    T data;                //结点的数据域
    int link;              //结点的指针域
};
///////////////////////////ListNode<T>结构定义结束

//////////////////////////////////////////////////
//StaticList<T>静态链表类的实现
//T是数据域的类型
//////////////////////////////////////////////////
template<class T>
class StaticList
{
private:
    int maxSize;           //链表的最大空间
    int currentSize;       //链表的当前含有的元素个数
    ListNode<T>* Vector;   //链表的结点数组
public:
    StaticList(int* arr,
        int n)             //构造函数
    {
        maxSize=n+10;
        currentSize=n;
        Vector=new ListNode<T>[maxSize];
        Vector[0].data=maxValue;
        Vector[0].link=1;  //初始化附加头结点,指向第一个结点
        for(int i=1;i<=currentSize;i++)
        {                  //初始化当前静态链表
            Vector[i].data=arr[i-1];
            Vector[i].link=0;
        };
    };
    void InsertSort();     //对当前的静态链表进行插入排序
    void LSDSort(int d);   //采用LSD方法(最小排序码优先)进行排序
    void Display()         //显示当前的已经链接好的有序表
    {
        int ptr=Vector[0].link;
        while(ptr!=0)
        {
            cout<<Vector[ptr].data<<" ";
            ptr=Vector[ptr].link;
        };
    };

    ~StaticList()          //析构函数
    {delete [] Vector;};
    T GetDigit(T x,int d); //获得x的第i个排序码
};
///////////////////////////StaticList<T>类声明结束

//////////////////////////////////////////////////
//InsretSort()公有成员函数
//对当前的静态链表进行直接插入排序
//////////////////////////////////////////////////
template<class T>
void StaticList<T>::InsertSort()
{
    int ptr=0;                        //游标指针
    for(int i=2;i<=currentSize;i++)
    {
        ptr=0;                        //指向已经排好序的链表的第一个元素
        do                            //寻找插入的位置
        {
            int next=Vector[ptr].link;//得到ptr下个结点的地址
            if(Vector[i].data<Vector[next].data)
            {                         //如果当前元素小于元素next
                Vector[i].link=next;  //把新结点i插入到ptr和next之间
                Vector[ptr].link=i;
                break;                //退出内层循环进行下次插入
            }
            ptr=Vector[ptr].link;
        }
        while(ptr!=0);               
    };
};
//////////////////////InsertSort()公有成员函数结束

//////////////////////////////////////////////////
//GetDigit()公有成员函数
//获得关键码x的第i个排序码,i从右往左依次是0,1,2...
//////////////////////////////////////////////////
template<class T>
T StaticList<T>::GetDigit(T x,int d)
{
    if(d==3)
        return int(x/1000);
    else if(d==2)
        return int(x%1000)/100;
    else if(d==1)
        return int(x%100)/10;
    else
        return int(x%10);
};
////////////////////////////////GetDigit()函数结束

//////////////////////////////////////////////////
//LSDSort()公有成员函数
//采用LSD的方法(最小关键码优先)的方法进行排序
//基本思想:先按排序码桶进行分配,再进行收集
//其中d是关键码的位数
//////////////////////////////////////////////////
template<class T>
void StaticList<T>::LSDSort(int d)
{
    /*设置每个桶队列的头尾指针*/
    int front[10];                 //10个桶队列的头指针数组
    int rear[10];                  //10个桶队列的尾指针数组

    /*把数据按初始顺序进行连接*/
    for(int i=0;i<10;i++)  
        Vector[i].link=i+1;
    Vector[i].link=0;              //构建单向循环链表

    /*进行d+1趟的分配和收集*/
    int p=0;
    while(p<=d)
    {
        /*首先初始化当前的队列指针*/
        for(i=0;i<10;i++)         
        {front[i]=-1;rear[i]=-1;};
        /*首先把第i个关键码按桶进行分配*/
        int ptr=Vector[0].link;    //链表遍历的游标指针
        while(ptr!=0)
        {
            T k=                   //获得第i个排序码
               GetDigit(Vector[ptr].data,p);   
            if(front[k]==-1)       //如果原来的队列是空的
            {
                front[k]=ptr;
                rear[k]=ptr;       //直接插入队列
            }
            else                   //如果队列不空
            {
                Vector[rear[k]].link=ptr;
                rear[k]=ptr;       //直接把结点挂入队列
            };

            ptr=Vector[ptr].link;  //指针向后推进一格
        };

        /*把当前元素收集起来重新链起来*/
        ptr=0;                     //游标指针
        for(i=0;i<10;i++)          //遍历当前所有的桶
        {
            if(front[i]!=-1)       //如果当前访问的桶不空
            {
                Vector[ptr].link=front[i];
                ptr=rear[i];       //把当前桶中的数据收集到链表中
            };
        };
        Vector[ptr].link=0;        //构建循环链表

        p++;
    };
};
/////////////////////////////////LSDSort()函数结束

#endif
这个算法表面上的复杂度低,d趟分配和收集,但问题仍然是getdigit()
的消耗的时间复杂度.