小小c#算法题 - 9 - 基数排序 (Radix Sort)

基数排序和前几篇博客中写到的排序方法完全不同。前面几种排序方法主要是通过关键字间的比较和移动记录这两种操作来实现排序的，而实现基数排序不需要进行记录项间的比较。而是把关键字按一定规则分布在不同的区域，然后再重新整合，使之有序，属于分布排序的一种。

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。

下面举一个书上的例子，扑克牌的排序。对于扑克牌，在比较任意两张牌的大小时（暂不考虑大王和小王），首先要比较花色，因为花色的“地位”高于面值，比如黑桃>红心>方片>梅花；然后是面值的大小A>13>12>...>2，所以这里扑克牌的排序就牵涉到两种关键字。那么怎么来排序呢？这里有两种：

1. 遍历52张牌，根据花色分成4堆（分配操作）。然后对每一堆按面值大小整理有序，即每一花色堆中的牌再分成13堆（分配操作），这已经比较到了最后一个关键字，不能再往下分了，这时每堆只有一张。到最后一共有52堆（可以称之为52个子序列），最后将这些子序列依次联接在一起（收集操作）成为一个有序序列。

2.遍历52张牌，根据面值分成13堆（分配操作）。然后把这13堆摞起来（收集操作），按这样的顺序：面值最小（即面值为2）的堆放最下面，然后依次往上放，面值最大（即面值为A）的堆放最上面。这样13堆就又变成了一堆，再次遍历这一堆52张牌，根据花色不同分成4堆（分配操作）。这时候每个花色堆中的牌都是按面值有序的，比如黑桃堆，黑桃A在最下面，黑桃2在最上面。这时再把这四个花色堆按花色顺序堆在一起（收集操作），那么所有52张牌就都是有序的了。如果把黑桃堆放最下面，依次往上，梅花堆放最上面，那么牌的顺序就是递增的，反之则是递减的。

由此可见，基数排序根据多关键字，借助“分配”和“收集”的操作，并未有记录间的比较，就能使待排序列有序。

上面两种不同的方法其实引出了两种不同的基数排序：
最高位优先（Most Significant Digit first）法，简称MSD法。
最低位优先（Least Significant Digit first）法，简称LSD法。

以下是摘自数据结构严蔚敏版中的定义：

一般情况下，假设有n个记录的序列

{R₁,R₂,...,R_n}

且每个记录R_i 中含有d个关键字(K_i², K_i¹, ..., K_i^d-1 )，则称R序列对关键字(K_i², K_i¹, ..., K_i^d-1 )有序是指：对于序列中任意两个记录R_i 和 R_j (1<=i<=j<=n)都满足下列有序关系：

(K_i², K_i¹, ..., K_i^d-1 ) < (K_j², K_j¹, ..., K_j^d-1 )

其中K⁰称为最主位关键字，K^d-1称为最次位关键字。

为实现多关键字排序，通常有两种方法：

第一种方法是：先对最主位关键字K⁰进行排序，将序列分成若干子序列，每个子序列中的记录都有相同的K⁰值，然后分别就每个子序列对关键字K¹进行排序，按K¹值不同再分成若干更小的子序列，依次重复，直到对K^d-2进行排序之后得到的每一子序列中的记录都有相同的关键字（K⁰, K¹, ... , K^d-2），而后分别每个子序列对K^d-1进行排序，最后将所有子序列依次联接在一起成为一个有序序列，这种方法称之为最高位优先法，简称MSD法。

第二种方法是从最次位关键字K^d-1起进行排序。然后再对高一位的关键字K^d-2进行排序，依次重复，直至对K⁰进行排序后便成为一个有序序列。这种方法称之为最低优先法，简称LSD法。

从上所述，可以看出两种排序方法的不同特点：

若按MSD进行排序，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序，到最后一个关键字时，一次收集所有子序列。这样貌似要更多的辅助存储空间。

若按LSD进行排序，每按关键字分成子序列后（一次分配），就进行一次收集操作。然后再遍历所有记录，按更主关键字再分配，然后再收集，... ，，所有针对每个关键字都是针对整个序列参加排序。用分配和收集操作可以实现排序，当然用前几篇博客中提到普通排序方法也可以，但这些排序方法必须是稳定的，这是显而易见的，比如，二位数集全中36和35的比较，这里其实有2个关键字，个位，十位。按LSD来，先比较个位，这时36在前，35在后，然后比较十位，由于都是3，如果是不稳定排序的话，那么他们两个的位置就有可能互换。从而导致非完全有序的序列。

好了，上面讲了好多理论知识，下面是一个链式基数排序的算法：

这里我们就拿整数的比较来讲，比较简单。每一位（个，十，百...）都是一个关键字，每个关键字的范围都是0~9。但其实，许多情况下针对不同的关键字可能有不同的取值范围，可能就要做一些相应的调整。

按所有记录存储在一个链表结构中，每个记录是链表的一个结点中的value。然后根据关键字的取值范围建立（0~9，共10个）10个子链表。遍历链表中的元素，比较个位，按个位的值，把结点添加相应的子链表的尾部。比如365的个位5，那么就放在第5个子链表的尾部。这样就完成了一次分配。

然后将子链表从第0个到第9个首尾相连起来：header0...tail0->header1...tail1->... ... ->header9...tail9。这样就完成了一次收集。

然后再根据十位来比较，根据十位的值装入不同子链表中（此时的子链表是新的，可以是新建的，可以是处理清空过的，代码处理一下即可）。这样又完成了一次分配。

然后再首尾相连，完成一次收集。

。。。这要一直下去，比较完所有关键字，位数。即完成序列的排序。

下面是代码：

先要建立自定义的链表结点和链表的数据结构，我这里简单写了一下：

    // 单链表
    class SingleLinkedList<T>
    {
        public MyLLNode<T> First
        {
            get;
            set;
        }

        public MyLLNode<T> Last
        {
            get;
            set;
        }

        public void AddLast(MyLLNode<T> node)
        {
            if (First == null)
            {
                First = node;
                Last = node;
                node.Next = null;
            }
            else
            {
                Last.Next = node;
                Last = node;
                node.Next = null;
            }
        }
    }

    // 单链表结点
    class MyLLNode<T>
    {
        public T Value
        {
            get;
            set;
        }

        public MyLLNode<T> Next
        {
            get;
            set;
        }
    }

下面是排序的代码：

        private static void RandixSort(int[] myArray,int keyNum)
        {
            SingleLinkedList<int> listArray = new SingleLinkedList<int>();
            foreach (int i in myArray)
            {
                listArray.AddLast(new MyLLNode<int>() { Value = i });
            }

            for (int i = ; i < keyNum; i++)
            {
                // 对每个关键字执行分配和收集操作
                DistributeAndCollect(listArray, i);
            }

            int j = ;
            while (listArray.First != null)
            {
                myArray[j++] = listArray.First.Value;
                listArray.First = listArray.First.Next;
            }
        }

        // 分配和收集
        private static void DistributeAndCollect(SingleLinkedList<int> listArray, int i)
        {
            int randix = ; //关键字取值范围
            int divider = (int)Math.Pow(, i);
            List<SingleLinkedList<int>> subLists = new List<SingleLinkedList<int>>(); //建立子序列
            for (int j = ; j < randix; j++)
            {
                subLists.Add(new SingleLinkedList<int>());
            }

            // 开始一次分配
            while (listArray.First != null)
            {
                int index = (listArray.First.Value / divider) % ;

                MyLLNode<int> tempNode=listArray.First.Next;
                subLists[index].AddLast(listArray.First);
                listArray.First = tempNode;
            }

            // 开始一次收集
            int k = ;
            for (; k < randix; k++)
            {
                if (subLists[k].First != null)
                {
                    // 找到第一个非空子序列以设置总序列的First值
                    listArray.First = subLists[k].First;
                    listArray.Last = subLists[k].Last;
                    break;
                }
            }

            // 找好子序列设置好listArray.First后，开始处理非空子序列的首尾相连
            for (; k < randix; k++)
            {
                if (subLists[k].First != null)
                {
                    listArray.Last.Next = subLists[k].First;
                    listArray.Last = subLists[k].Last;
                }
            }
        }

再次强调一点，只是这个示例中的每个关键字的处理情况一样，所以DistributeAndCollect方法中的处理比较简单，有时候需要针对不同的关键字作相应的调整，比如randix取值范围不一样的情况。

下面的调用：

　　　　 static void Main(string[] args)
        {
            int[] numbers = { , , , , , , , , , , , ,  };
            RandixSort(numbers, );

            foreach (int i in numbers)
            {
                Console.Write(i.ToString() + " ");
            }
            Console.Read();
        }

最后，针对这个例子能看出，对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围是randix个值）进行链式基数排序的时间复杂度为O(d(n+randix))，其中每一趟分配的时间复杂度为O(n),第一趟收集的时间复杂度为O(randix)[因为有randix个子链表]，整个排序需进行d趟分配和收集。所需辅助空间为2*randix个引用，其实每个子序列也就保存了首尾两个引用，结点还是那么些个结点，只不过通过设置next指针把其分开了而已。

好了，这就是基数排序的全部内容。