首页 > 代码库 > 【sort】 基数排序
【sort】 基数排序
下面这段问答摘自csdn：
把基数排序说成桶排序应该是没有太大问题的。
总的说来，应该把这一类归为分配排序，由于分配排序的一些缺陷，主要是时间代价很差，改进成为桶式排序（bucket sort），而桶排序的基本思路是将较少的纪录分配到每个桶，然后用较快的“收尾排序”来对每桶中的纪录进行排序。在此基础上，当允许基于分配排序的收尾排序时，为了尽量减少桶的数量并缩短排序时间，发展出了基数排序（Radix Sort）。
基数的选择：如果是数字，最常用的是2和10这两个了，当然是由于二进制和十进制的关系，就如楼上的那种表示方法：8 = 0 * 2 ^ 1 + 0 * 2 ^ 2 + 1 * 2 ^ 3
同样，有：162 = 2 * 10 ^ 0 + 6 * 10 ^ 1 + 1 * 10 ^ 2
还记得基数、基码、位权吧，基数决定桶数，基码决定了桶的位置先后，位权决定分配次数。
如果是字符串，当然是26了（26个字母），呵呵。
至于“在位内进行比较的时候采用什么排序法？？？”
猜想意思是：把高位比较了一次之后，分到了不同的桶里，在桶内再将所有的数作一次排序。如果是那样的话，就只能叫桶排序了，就不能体现出基数排序的优越性。
在具体实现时，基数排序应该是没有比较大小这一过程的，而只是将待排序的数字什么的做分配的一个过程，只要看位权就可以决定到底做几次分配了（3位数就做3次分配）。
下面是一个例子：
待排序列表：27 91 1 97 17 23 84 28 72 5 67 25
基数是10，基码是0~9，最大的位权是1（决定了分配次数是1+1=2）。
第一趟分配：（先排个位数）
桶的编号 分配到桶内的数字
0
1 -> 91 -> 1
2 -> 72
3 -> 23
4 -> 84
5 -> 5 -> 25
6
7 -> 27 -> 97 -> 17 -> 67
8 -> 28
9
第一趟分配结果是（从0号桶开始，得到这个序列）：91 1 72 23 84 5 25 27 97 17 67 28
然后在此基础上作第二次分配：（排十位数）
桶的编号 分配到桶内的数字
0 -> 1 -> 5
1 -> 17
2 -> 23 -> 25 -> 27 -> 28
3
4
5
6 -> 67
7 -> 72
8 -> 84
9 -> 91 -> 97
第二趟分配的结果是（从0号桶开始，得到这个序列）：1 5 17 23 25 27 28 67 72 84 91 97
好了，这就是我们所需要的了。由于第一次的结果已经使个位数保持递增，第二次只要在此基础上使十位数递增即可，不用考虑个位数的大小，这样两次分配就可以达到排序目的了。
#include <cstdio>#include <iostream>#include <stdlib.h>using namespace std;int RadixCountSort(int*index, int maxn, int* nData, int len){ int* cnt= (int*)malloc(sizeof(int)* maxn); for (int i=0;i<len;i++) { cnt[i] = 0; } for (int i=0;i<len;i++) { cnt[index[i]]++; } for (int i=1;i<10;i++) //确定不大于该位置的个数。 { cnt[i]+=cnt[i-1]; } int *tmp=(int*)malloc(sizeof(int)*len); //存放临时的排序结果。 for (int i=len-1;i>=0;i--) { cnt[index[i]]--; tmp[cnt[index[i]]] = nData[i]; } for (int i=0;i<len;i++) { nData[i] = tmp[i]; } free(tmp); free(cnt); return 1;}int RadixSort(int* nData,int len){ int *Radix=(int*)malloc(sizeof(int)*len); int Base = 1; bool check = false; while (!check) { check = true; Base *= 10; for (int i=0;i<len;i++) { Radix[i] = nData[i] % Base; Radix[i] /= Base / 10; if (Radix[i]>0) check=false; } if (check)break; //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。 RadixCountSort(Radix, 10, nData, len); } free(Radix); return 1; }int main(){ int Data[10]={123,5264,9513,854,9639,1985,159,3654,8521,8888}; RadixSort(Data, 10); for (int i=0;i<10;i++) printf("%d ",Data[i]); printf("\n"); system("pause"); return 0;}
【sort】 基数排序