算法总结系列之五: 基数排序(Radix Sort)

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位)

第一次排序(个位):

3 4 2

5 7 6

3 5 6

0 5 8

第二次排序(十位):

3 4 2

3 5 6

0 5 8

5 7 6

第三次排序(百位):

0 5 8

3 4 2

3 5 6

5 7 6

结果: 58 342 356 576

两个问题:

• 为什么要从低位开始向高位排序?

        如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大.从低位开始排序,就是对这种影响的排序. 数位按照影响力从低到高的顺序排序, 数位影响力相同则比较数位值.

• 为什么同一数位的排序子程序要使用稳定排序?

        稳定排序的意思是指, 待排序相同元素之间的相对前后关系,在各次排序中不会改变.比如实例中具有十位数字5的两个数字58和356, 在十位排序之前356在58之前,在十位排序之后, 356依然在58之前.

        稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.

算法的C#实现(综合了计数排序算法作为数位内排序算法):

public static int[] RadixSort(int[] ArrayToSort, int digit)

{

//low to high digit

for (int k = 1; k <= digit; k++)

{

//temp array to store the sort result inside digit

int[] tmpArray = new int[ArrayToSort.Length];

//temp array for countingsort

int[] tmpCountingSortArray = new int[10]{0,0,0,0,0,0,0,0,0,0};

//CountingSort

for (int i = 0; i < ArrayToSort.Length; i++)

{

//split the specified digit from the element

int tmpSplitDigit = ArrayToSort[i]/(int)Math.Pow(10,k-1) - (ArrayToSort[i]/(int)Math.Pow(10,k))*10;

tmpCountingSortArray[tmpSplitDigit] += 1; 

}

for (int m = 1; m < 10; m++)

{

tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];

}

//output the value to result

for (int n = ArrayToSort.Length - 1; n >= 0; n--)

{

int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10,k - 1) - (ArrayToSort[n]/(int)Math.Pow(10,k)) * 10;

tmpArray[tmpCountingSortArray[tmpSplitDigit]-1] = ArrayToSort[n];

tmpCountingSortArray[tmpSplitDigit] -= 1;

}

//copy the digit-inside sort result to source array

for (int p = 0; p < ArrayToSort.Length; p++)

{

ArrayToSort[p] = tmpArray[p];

}

}

return ArrayToSort;

}

这个算法的难度在于分离数位,将分离出的数位代表原元素的代表, 用作计数排序.但是分离数位不能脱离原来的数字,计数排序的结果,还是要移动原元素.

注意计数排序的元素数值与位置的联系,引申到基数排序的从元素得到中间值然后与位置的联系.

测试程序如下:

static void Main(string[] args)

{

int[] ary = new int[] { 332, 653, 632, 755, 433, 722, 48 };

int[] res = RadixSort(ary, 3);

foreach (int vr in res)

{

Console.Write(vr.ToString() + " ");

}

Console.ReadLine();

}

作者：Jeffrey Sun
出处：http://sun.cnblogs.com/
本文以“现状”提供且没有任何担保，同时也没有授予任何权利。本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。