顺序基数排序算法

1. 适用范围:

适用范围:

1. 稍加改造即可用于多关键字排序
2. 关键字取值范围较小
3. 正统的基数排序只适用于正整数
   1. 稍加改造才能用于实数 优点:
4. 关键字小的时候速度比快速排序要快
   1. 时间复杂度位O(子关键字数量×n)
5. 空间复杂度比计数排序低 缺点:
6. 空间复杂度为O(n)

2. 梗概:

1. 利用排序的稳定性, 先排序最低位, 再依次排序更高位, 直到最高位也排完

3. 算法思想:

1. 把记录中的关键字拆分为优先级从高到低的关键字(通常按照10进制的位数分)
2. 从低位到高位, 逐位排序, 最后有序

4. 在c语言中的实现

```c
typedef struct{
	KeyType key;
}RecordType;
#define BASE 10
void radixsort(RecordType records[], int len){
	/*exp配合基数BASE指定位数*/
	int i,exp=1;
	KeyType maxk = records[0].key;
	RecordType* b=(RecordType*)calloc(len,sizeof(RecordType));
	/*找最大关键字,决定要排到多少位*/
	for (i = 1; i < len; i++)
		if (records[i].key > maxk)
			maxk = records[i].key;
	/*从低位到高位排序*/
	for(;maxk/exp > 0;exp *= BASE){
		int bucket[BASE] = {0};
		/*在计数桶上存储该位上相同的记录数量*/
		for (i = 0; i < len; i++)
			bucket[(records[i].key / exp) % BASE]++;
		/*当前计数桶中的记录数量+前面桶的记录数量
		可决定当前计数桶中记录排序后的位置*/
		for (i = 1; i < BASE; i++)
			bucket[i] += bucket[i - 1];
		/*根据对应计数桶中存储的位置把该数都放到其应在的位置*/
		/*保持稳定性:因为同一个计数桶中存储的位置从右往左,
		所以关键字也要从右往左遍历*/
		for (i = len - 1; i >= 0; i--){
			/*同一个计数桶中取了记录,下一个位置就要往左移动*/
			int pos = --bucket[(records[i].key / exp) % BASE];
			/*b用来暂时存储排序好的记录,防止覆盖原记录数组*/
			b[pos] = records[i];
		}
		for (i = 0; i < len; i++)
			records[i] = b[i];
	}
	free(b);
}