基数排序

发表于 | 分类于 | 阅读次数: |
字数统计: 340

一：基数排序（桶排序）介绍：

1574689896893

基数排序基本思想：

1574690002482

图文说明：

1574690131194

二：思想分析

1574690459936

1574690489690

1574690519996

三：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
static void Main(string[] args)
       {
           int[] arr = { 34, 75, 489, 9, 123, 3 };
           radixSort(arr);
           print(arr);
           Console.ReadKey();
       }

       //基数排序方法
       public static void radixSort(int[] arr)
       {
           int[,] bucket = new int[10, arr.Length];
           int[] bucketElementCounts = new int[10];

           #region 去数组中的长度最长的数
           int max = 0;
           for (int i = 0; i < arr.Length; i++)
           {
               if (arr[i] > max)
               {
                   max = arr[i];
               }
           }
           max = max.ToString().Length;
           #endregion

           for (int m = 0, n = 1; m < max; m++, n *= 10)
           {
               #region 按照遍历的顺序，将数存入桶中，个位，十位...
               for (int i = 0; i < arr.Length; i++)
               {
                   //取出每个元素的个位
                   int digitOfElement = arr[i] / n % 10;
                   //放入对应的桶
                   bucket[digitOfElement, bucketElementCounts[digitOfElement]] = arr[i];
                   bucketElementCounts[digitOfElement]++;
               }
               #endregion

               #region 遍历桶，将数据重新写会数组汇中
               int index = 0;
               //遍历每一个桶
               for (int i = 0; i < bucketElementCounts.Length; i++)
               {
                   //如果桶有数据，我们才放到原数据中
                   if (bucketElementCounts[i] != 0)
                   {
                       //循环该桶
                       for (int k = 0; k < bucketElementCounts[i]; k++)
                       {
                           //取出元素放入arr
                           arr[index++] = bucket[i, k];
                       }
                   }
                   bucketElementCounts[i] = 0;
               }
               #endregion
           }
       }
       /// <summary>
       /// 打印
       /// </summary>
       /// <param name="arr"></param>
       public static void print(int[] arr)
       {
           for (int i = 0; i < arr.Length; i++)
           {
               Console.Write(arr[i] + "\t");
           }
           Console.WriteLine("");
       }

四：源码地址

Github-基数排序