波斯马BOSSMA Information Technology

C#排序算法之基数排序

发布时间:2010年9月14日 / 分类:DOTNET / 7,547 次浏览 / 评论

基数排序属于“分配式排序”,基数排序法又称“桶子法”,顾名思义,它是透过键值的部份信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序。基数排序的方式可以采用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);
        }

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

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《C#排序算法之基数排序

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论