C#排序算法之基数排序

发布时间：2010年9月14日 / 分类：DOTNET / 8,620 次浏览 / 评论

基数排序属于“分配式排序”，基数排序法又称“桶子法”，顾名思义，它是透过键值的部份信息，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

以LSD为例，假设有一串数值如下：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶中：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕。

思路比较简单，看看如何用C#实现：

/// <summary>
        /// 基数排序
        /// </summary>
        /// <param name="intArr"></param>
        static void RadixSort(int[] intArr)
        {
            //初始化10个桶
            List<int>[] listArr = new List<int>[10];
            for (int i = 0; i < listArr.Length; i++)
            {
                listArr[i] = new List<int>();
            }

            int maxLength = GetMaxLength(intArr);

            //遍历位数，从个位开始
            for (int i = 1; i <= maxLength; i++)
            {
                string currentItem = string.Empty;
                char itemCurrentChar;
                foreach (int item in intArr)
                {
                    currentItem = item.ToString();
                    if (currentItem.Length >= i)
                    {
                        itemCurrentChar = currentItem[currentItem.Length - i];
                    }
                    else//如果尾数不够，直接加入0桶
                    {
                        listArr[0].Add(item);
                        continue;
                    }

                    //根据当前位数的值加入不同的桶
                    switch (itemCurrentChar)
                    {
                        case '0':
                            listArr[0].Add(item);
                            break;
                        case '1':
                            listArr[1].Add(item);
                            break;
                        case '2':
                            listArr[2].Add(item);
                            break;
                        case '3':
                            listArr[3].Add(item);
                            break;
                        case '4':
                            listArr[4].Add(item);
                            break;
                        case '5':
                            listArr[5].Add(item);
                            break;
                        case '6':
                            listArr[6].Add(item);
                            break;
                        case '7':
                            listArr[7].Add(item);
                            break;
                        case '8':
                            listArr[8].Add(item);
                            break;
                        case '9':
                            listArr[9].Add(item);
                            break;
                    }
                }

                //将十个桶的数字重新放入数组
                int j = 0;
                for (int k = 0; k < listArr.Length; k++)
                {
                    foreach (int p in listArr[k])
                    {
                        intArr[j] = p;
                        j++;
                    }

                    listArr[k].Clear();
                }
            }

            DisplaySortResult(0, 0, intArr);
        }

其中用到了某些高级的数据结构，可能对性能有一定影响，因此下边的数据不具有很大的可比性。