发布时间 : 星期日 文章排序算法集合更新完毕开始阅读4a37d1e3caaedd3382c4d336
果。
其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后将这十三堆牌按面值从小到大的顺序叠放在一起，再把整副牌按顺序根据花色再分成四堆（每一堆牌已按面值从小到大的顺序有序），最后将这四堆牌按花色从小到大合在一起就得到排序的结果。
——————————————————————————————————————— 实现方法：
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 ---------------------------------Code in C#------------------------------------------ using System;
using System.Collections.Generic; using System.Linq; using System.Text; namespace LearnSort {
class Program {
static void Main(string[] args) {
int[] arr = CreateRandomArray(10);//产生随机数组 Print(arr);//输出数组 RadixSort(ref arr);//排序 Print(arr);//输出排序后的结果 Console.ReadKey(); }
public static void RadixSort(ref int[] arr) {
int iMaxLength = GetMaxLength(arr); RadixSort(ref arr, iMaxLength); }
private static void RadixSort(ref int[] arr, int iMaxLength) {
List
char currnetChar;//存放当前的字符比如说某个元素123 中的2
string currentItem;//存放当前的元素比如说某个元素123
for (int i = 0; i < listArr.Length; i++)//给十个桶分配内存初始化。 listArr[i] = new List
for (int i = 0; i < iMaxLength; i++)//一共执行iMaxLength次，iMaxLength是元素的最大位数。 {
foreach (int number in arr)//分桶 {
currentItem = number.ToString();//将当前元素转化成字符串
try { currnetChar = currentItem[currentItem.Length-i-1]; }//从个位向高位开始分桶 catch { listArr[0].Add(number); continue; }//如果发生异常，则将该数压入listArr[0]。比如说5 是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。
switch (currnetChar)//通过currnetChar的值，确定它压人哪个桶中。 {
case '0': listArr[0].Add(number); break; case '1': listArr[1].Add(number); break; case '2': listArr[2].Add(number); break; case '3': listArr[3].Add(number); break; case '4': listArr[4].Add(number); break; case '5': listArr[5].Add(number); break; case '6': listArr[6].Add(number); break; case '7': listArr[7].Add(number); break; case '8': listArr[8].Add(number); break; case '9': listArr[9].Add(number); break; default: throw new Exception(\ } }
for (int j = 0; j < listArr.Length; j++)//将十个桶里的数据重新排列，压入list foreach (int number in listArr[j].ToArray
list.Add(number);
listArr[j].Clear();//清空每个桶 }
arr = list.ToArray
}
//得到最大元素的位数
private static int GetMaxLength(int[] arr) {
int iMaxNumber = Int32.MinValue; foreach (int i in arr)//遍历得到最大值 {
if (i > iMaxNumber) iMaxNumber = i; }
return iMaxNumber.ToString().Length;//这样获得最大元素的位数是不是有点投机取巧了... }
//输出数组元素
public static void Print(int[] arr) {
foreach (int i in arr)
System.Console.Write(i.ToString()+'\\t'); System.Console.WriteLine(); }
//产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数 public static int[] CreateRandomArray(int iLength) {
int[] arr = new int[iLength]; Random random = new Random(); for (int i = 0; i < iLength; i++) arr[i] = random.Next(0,1001); return arr; } } }
---------------------------------Code --------------------------------------------- 基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。