排序七:基数排序

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace RadixSort
  8 {
  9     class Program
 10     {
 11         static void Main(string[] args)
 12         {
 13             int[] arr = new int[10];
 14             Random rd = new Random();
 15             for (int i = 0; i < arr.Length; i++)
 16             {
 17                 arr[i] = rd.Next(10000);
 18             }
 19             RadixSort(arr, 4);
 20         }
 21         //基数排序-最低位优先法【LSD(Least significant digital)】
 22         public static void RadixSort(int[] arr, int numberMaxLength)
 23         {
 24             //存放每次排序后的元素
 25             List<int> list = new List<int>();
 26             //十个桶
 27             List<int>[] listArr = new List<int>[10];
 28             //存放当前元素
 29             string currentItem;
 30             //存放当前元素中的字符
 31             char currentChar;
 32             //给十个桶分配内存初始化
 33             for (int i = 0; i < listArr.Length; i++)
 34             {
 35                 listArr[i] = new List<int>();
 36             }
 37             //一共执行numberMaxLength次,numberMaxLength是元素的最大位数
 38             for (int i = 0; i < numberMaxLength; i++)
 39             {
 40                 foreach (int number in arr)
 41                 {
 42                     //当前元素转成字符串
 43                     currentItem = number.ToString();
 44                     try
 45                     {
 46                         //从个位向高位开始分桶
 47                         currentChar = currentItem[currentItem.Length - i - 1];
 48                     }
 49                     catch
 50                     {
 51                         //如果发生异常,则将该数压入listArr[0]。比如说5是没有十位数的,
 52                         //执行上面的操作肯定会发生越界异常的,这正是期望的行为,我们认为5的十位数是0,
 53                         //所以将它压入listArr[0]的桶里。
 54                         listArr[0].Add(number);
 55                         continue;
 56                     }
 57                     switch (currentChar)
 58                     {
 59                         case 0:
 60                             listArr[0].Add(number);
 61                             break;
 62                         case 1:
 63                             listArr[1].Add(number);
 64                             break;
 65                         case 2:
 66                             listArr[2].Add(number);
 67                             break;
 68                         case 3:
 69                             listArr[3].Add(number);
 70                             break;
 71                         case 4:
 72                             listArr[4].Add(number);
 73                             break;
 74                         case 5:
 75                             listArr[5].Add(number);
 76                             break;
 77                         case 6:
 78                             listArr[6].Add(number);
 79                             break;
 80                         case 7:
 81                             listArr[7].Add(number);
 82                             break;
 83                         case 8:
 84                             listArr[8].Add(number);
 85                             break;
 86                         case 9:
 87                             listArr[9].Add(number);
 88                             break;
 89                         default:
 90                             throw new Exception("unknow error");
 91                     }
 92                 }
 93                 //清空list
 94                 list.Clear();
 95                 //将十个桶里的数据重新排列,压入list
 96                 for (int j = 0; j < listArr.Length; j++)
 97                 {
 98                     foreach (int number in listArr[j].ToArray<int>())
 99                     {
100                         list.Add(number);
101                         //清空每个桶
102                         listArr[j].Clear();
103                     }
104                 }
105                 //arr指向重新排列的元素
106                 arr = list.ToArray<int>();
107             }
108             foreach (int i in list)
109             {
110                 Console.WriteLine(i);
111             }
112         }
113     }
114 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。