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