数据结构与算法基数排序报告讲解.pptx

基数排序(Radix sort) 基数排序原理： 将所有待比较数值（正整数）统一为同样的数位长度，这里采取数位较短的数前面补零。 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 基数排序的时间复杂度是 O(n)， 更准确的说是O(kn)，其中n是排序元素个数，k是数字位数。 一种基于分配—收集的排序算法一种稳定的排序算法 扩展：稳定的排序算法： 计数排序 插入排序 归并排序 最低位优先法： 首先是按照最低有效位数字进行排序，然后再按次低有效位，知道对所有的数字都进行排序。对于d位数来说，仅需d遍就可以将一个数组排好序 多关键字排序 最高位优先法(MSD) 最低位优先法（LSD） Eg1.待排序数组[62,14,59,88,16] 分配10个可重复利用的桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样 |? 0? |? 0? | 62 |? 0? | 14 |? 0? | 16 |? 0? |? 88 | 59 | |? 0? |? 1? |? 2? |? 3? |? 4 |? 5? |? 6? |? 7? |? 8? |? 9? |桶编号 将桶里的数字顺序取出来,输出结果:[62,14,16,88,59] 再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序 |? 0? | 14,16 |? 0? |? 0? |? 0? | 59 | 62? | 0? | 88? |? 0? | |? 0? |? 1????? |? 2? |? 3? |? 4? |? 5? |? 6? |? 7? |? 8? |? 9? |桶编号 因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可 最后输出结果:[14,16,59,62,88] 基数排序过程图示：红色表示当前正被排序的数位。 Eg2.待排序数组 [329,457,657,839,436,720,355] 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; }