排序算法(6)——基数排序

[转载] 《算法导论》 [转载] http://www.cppblog.com/shongbee2/archive/2009/04/24/80992.html

1、基数排序的思想

如下图所示

1）、基数排序是从最低位开始的。如果从最高位先排序，次高位排序必须是在前者的基础上，不能打乱了最高位已排好的顺序，只能对最高位相同的次高位进行排序。

[例如] 一个无序数列{655 392 694 436 29 826 171 180}; 先从最高位排序：{826 694 655 436 392 171 180 29}; 再对次高位排序：只能对高位是6的{694 655}单独排序，对高位是1的{171 180}单独排序。

后果是为了排序1个容器，另外9个容器都必须先放在一边，这个过程要保存很多的临时变量。所以从最高位开始排序不可取，要从低位开始。 2）、基数排序是仅根据一位的相对大小，改变一次这个数据的相对顺序。从低位到高位一轮调整下来，整个数组就是顺序排列的。 3）、要借助于稳定的排序算法来对一位（十进制就是0~9）进行排序。像冒泡排序，插入排序，计数排序排序算法都是稳定的。

2、基数排序的实现

#include <stdio.h> #include <stdlib.h> /************************************************* 函数功能：计数排序 函数参数： npRadix 对应的关键字序列， nMax 关键字的范围。 pData 具体要排的数据， length 数据的范围 ************************************************/ int count_sort(int* pIndex, int nMax, int* pData, int length) { //计数排序。不过这里为了是排序稳定 int* pCount = (int*)malloc(sizeof(int)* nMax); //保存计数的个数 for (int i = 0; i < nMax; ++i) pCount[i] = 0; for (int i = 0; i < length; ++i) //初始化计数个数 ++pCount[pIndex[i]]; for (int i = 1; i < 10; ++i)//确定不大于该位置的个数。 pCount[i] += pCount[i - 1]; //为了使排序稳定，i要从length-1到0的顺序排序 int * pnSort = (int*)malloc(sizeof(int) * length); for (int i = length - 1; i >= 0; --i) { --pCount[pIndex[i]]; pnSort[pCount[pIndex[i]]] = pData[i]; } for (int i = 0; i < length; ++i) pData[i] = pnSort[i]; free(pnSort); free(pCount); return 1; } //基数排序 int radix_sort(int* pData, int length) { //申请存放基数的空间 int* nDataRadix = (int*)malloc(sizeof(int) * length); //初始化 int nRadixBase = 1; //倍数基数：1 bool nIsOk = false; //完成排序状态：false //循环，直到排序完成 while (!nIsOk) { nIsOk = true; nRadixBase *= 10; for (int i = 0; i < length; ++i) { nDataRadix[i] = pData[i] % nRadixBase/(nRadixBase/10); if (pData[i]/nRadixBase > 0) nIsOk = false; } if (nIsOk) //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。 break; RadixCountSort(nDataRadix, 10, pData, length); } free(nDataRadix); return 1; } int main() { //测试基数排序。 int data[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888}; radix_sort(data, 10); for (int i = 0; i < 10; ++i) printf("%d ", data[i]); printf("\n"); system("pause"); return 0; }

3、基数排序的性能

1）、时间复杂度 时间复杂度是O(n)。对d位数进行排序，要从低位到高位做d个循环，每个循环是对一位的计数排序只是O(n)，算下来是O(d*n)，即O(n)。 2）、稳定性 基数排序是稳定的排序算法。因为在对一位排序时，基数排序使用了其它稳定的排序算法，这样它自身也是稳定的。 和其它层算法的比较： 基数排序和冒泡排序、插入排序一样，都是稳定的。 基数排序时间复杂度貌似最小，才O(n)。 基数排序要借助于其它的稳定排序算法，来对一位进行排序。