[考试]基数排序

[考试]基数排序 基数排序 一、基数排序算法描述 对数据元素进行排序的一种方法，是关键字为整数类型时非常高效的方法。 二、基数排序算法的基本思想 设待排序的数据元素关键字是m位d进制整数(不足m位的关键字在高位补零，设置d个桶，令其编号分别为0,1,2, …,d-1.首先，按关键字最低位的数值依次把各元素放到相应的桶中;然后，按照桶号从小往大和进入桶中数据元素的向后次序收集分配在各桶中的数据元素;这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序;再对一次基数排序得到的数据元素序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素;这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。 三、基数排序算法实现方法 基数排序算法进出桶中的数据元素序列满足先进先出的原则，桶实际就是队列。实现基数排序算法时，有基于顺序队列和基于链式队列两种不同的实现方法 四、采用链式队列来实现的过程 在基于链式队列的基数排序算法中，可以把d个队列成一个队列数组(设队列数组名为tub)，队列数组的每个元素中包括两个域: front域和rear域。front域用于指示队头，rear域用于指示队尾。当第i(i=0,1,2,…,d-1)个队列中有数据元素要放入时，就在队列数组的相应元素tub[i]中的队尾位置插入一个结点。基于链式队列基数排序算法的存储结构示意图如下图所示。 一个十进制关键字K的第i位数值Ki的计算公式为: KKK,int(),10，[int()](i,1,2,...,m)i,1i1010i 五、基于链式队列的基数排序算法 #include "LQueue.h" void RadixSort(DataType a[], int n, int m, int d) { int i, j, k, power = 1; LQueue *tub; //把d个队列定义为动态数组 tub = (LQueue *)malloc(sizeof(LQueue )* d); for(i = 0; i < d; i++) QueueInitiate(&tub[i]); //d个队列分别初始化 for(i = 0; i < m; i++) //进行m次放和收 { if(i == 0) power = 1; else power = power *d; for(j = 0; j < n; j++) //放 { k = a[j].key /power - (a[j].key /(power * d)) * d; QueueAppend(&tub[k], a[j]);//把a[j]放入第k个队列 } k = 0; for(j = 0; j < d; j++) //回收 while(QueueNotEmpty(tub[j]) != 0) { QueueDelete(&tub[j], &a[k]);//从各队列中回收 k++; } } } 六、基数排序算法分析 特点:不用比较和移动，改用分配和收集，时间效率高～ 时间复杂度为:O (mn)。 空间复杂度:O(n). 稳定性:稳定。(一直前后有序)。 七、基数排序算法测试实例 设待排序的数据元素有10个，数据元素的关键字序列{710,342,045,686,006, 841,429,134,068,264} 八、基数排序算法测试实例排序过程 九、基数排序算法测试主程序 #include #include typedef int KeyType; typedef struct { KeyType key; } DataType; void main(void) { DataType test[]={710, 342, 45, 686, 6, 841, 429, 134, 68, 246}; int i, n = 10, m = 3, d = 10; RadixSort(test, n, m, d); for(i = 0; i < n; i++) printf("%d \n", test[i].key); } 十、基数排序算法测试结果