数据结构与算法基数排序报告.pptxVIP

基数排序(Radix sort);基数排序原理：;一种基于分配—收集的排序算法一种稳定的排序算法;Eg1.待排序数组[62,14,59,88,16];基数排序过程图示：红色表示当前正被排序的数位。;void RadixSort(int *list, int begin, int end, int digit) { int radix = 10; //基数 int i = 0, j = 0; int * count = new int[radix]; //存放各个桶的数据存放个数 int * bucket = new int[end - begin + 1]; for (int d = 1; d = digit; d++) { for ( i = 0; i radix; i++) count[i] = 0; //置空各个桶的统计数据 for (i = begin; i = end; i++) { j = getDigit(list[i], d); count[j]++; } ; for (i = 1; i radix; i++) count[i] = count[i] + count[i - 1]; //count[i]表示第i个桶的右边界索引 //将数据依次装入桶中，保证数据的稳定性，此步即为基数排序的分配 for (i = end; i = begin; i--) { j = getDigit(list[i], d); bucket[count[j] - 1] = list[i]; count[j]--; } //基数排序的收集 //把桶中的数据再倒出来 for (i = begin, j = 0; i = end; i++, j++) list[i] = bucket[j]; } };其中 //此函数的目的是取得数据每个位上的数值 //i为待取的数据 int getDigit(int i, int d) //d的值为1、2、3...，表示要求取的相应位的值，1表示求取个位， { //2表示十分位，类推 int val; while (d--) { val = i % 10; i /= 10; } return val; } ;算法实现中， 我们用了两个数组：count[radix], bucket[end-begin+1]。 radix为基数，即桶的个数， 首先用第一个for循环，count[i]表示第i个桶中装入了几个数据， 接着用第二个for循环，标记在每个桶中，最后一个数据在整个数组中的右边界。 例如：第一个for循环结束后，count[0]=1，count[1]=count[2]=0，count[3]=2；在第二个for循环后，count[0]=1,count[1]=count[2]=1,count[3]=3，表示第三个桶中最后一个元素在数组中第三个位置。 其中 bucket[]的大小与待排序数组大小一样，是在排序中做收集步骤用。 digit表示各个数据的最大位数。 ;链式的基数排序算法;Eg3.待排序序列[278,109,063,589,184,505,269,608,083] ; 第一趟收集：按当前关键字位取值从小到大将各队列首尾相链成一个链表；（从队列的下面出去，先进先出） 进行第二趟分配，kd-2位 进行第二题收集 ;进行第三趟分配，也就是 kd-3位。本例子是 k1位关键字 进行第三趟收集 序列按照多关键字从小到大的排序有序了 ;链式队列的基数排序算法;//将初始队列中的元素分配到十个队列中,maxlen 代表了需要分配和收集的次数 for(int i = 0; i maxLen; i++) { Node *p = que.front-next; //辅助指针 q Node *q; //余数为k，则存储在arr[k]指向的链式队列（桶）中 int k; //遍历原始序列 while (p != NULL) { //重要的技巧，数据分离算法过程,最后勿忘模10，取余数，分离出需要的关键字位