波斯马BOSSMA Information Technology

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

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

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

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

0 　　

1 81

2 22 　　

3 73 93 43 　　

4 14 　　

5 55 65 　　

6 　　

7 　　

8 28 　　

9 39

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

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

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

0 　　

1 14 　　

2 22 28 　　

3 39 　　

4 43 　　

5 55 　　

6 65 　　

7 73 　　

8 81 　　

9 93

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

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);
        }

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

关键字: 基数排序 排序算法