截图
简介
这是基数排序ppt，包括了基数排序原理，一种基于分配—收集的排序算法一种稳定的排序算法，基数排序算法的具体实现，链式的基数排序算法等内容，欢迎点击下载。
基数排序ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
基数排序(Radix sort) 基数排序原理： 将所有待比较数值（正整数）统一为同样的数位长度，这里采取数位较短的数前面补零。 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后， 数列就变成一个有序序列。 基数排序的时间复杂度是 O(n)， 更准确的说是O(kn)，其中n是排序元素个数，k是数字位数。 一种基于分配—收集的排序算法 一种稳定的排序算法 扩展：稳定的排序算法： 计数排序 插入排序 归并排序 最低位优先法： 首先是按照最低有效位数字进行排序，然后再按次低有效位，知道对所有的数字都进行排序。对于d位数来说，仅需d遍就可以将一个数组排好序 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] 基数排序过程图示：红色表示当前正被排序的数位。 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表示各个数据的最大位数。 链式的基数排序算法 原理： 1、以静态链表存储待排记录，并令表头指针指向第一个记录； 2、“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同； 3、“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表； 4、对每个关键字位均重复 2 和 3 两步。 Eg3.待排序序列[278，109，063，589，184，505，269，608，083] 链式基数排序，下面以静态链表存储待排记录，并令表头指针指向第一个记录 “分配” 时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的 “关键字位” 相同。 因为是 LSD，故从地位开始 ，也就是kd-1位开始，进行一趟分配： 然后xx9，xx3，xx0 又遇到了 xx9，那么按照链式队列的存储方式，先进先出的入队（类似一个桶，数据从上面进入，从下面露出） 第一趟收集：按当前关键字位取值从小到大将各队列首尾相链成一个链表；（从队列的下面出去，先进先出） 进行第二趟分配，kd-2位 进行第二题收集 进行第三趟分配，也就是 kd-3位。本例子是 k1位关键字 进行第三趟收集 序列按照多关键字从小到大的排序有序了 链式队列的基数排序算法 void RadixSort(Queue& que) { //声明一个指针数组，该指针数组中存放十个指针，这十个指针需要分别指向十个队列，这是模拟10个桶，因为是0-9的数字，取值范围为10 Queue *arr[10]; //初始化这十个队列 for (int i = 0; i < 10; i++) { //初始化建立头结点 arr[i] = new Queue; } //取得待排序数据元素中的最大位数 int maxLen = que.lengthData(); //因为是 LSD 方式，从后到前，开始比较关键字，然后分配再收集，故开始设置数据分离算法中的除数为 1 int d = 1; //将初始队列中的元素分配到十个队列中，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，取余数，分离出需要的关键字位 k = (p->data / d) % 10; q = p->next; //把本结点 p 加入对应的队列中 arr[k]->push(p); //指针后移，指向下一个结点 p = q; } //清空原始队列 que.clear(); //分配完毕，马上将十个队列中的数据收集到原始队列中 for (int i = 0; i < 10; i++) { if (!arr[i]->empty()) { //从首节点开始遍历，不是头结点开始 Node *p = arr[i]->front->next; //辅助指针 q Node *q; while (p != NULL) { q = p->next; //收集到原始队列中，这就是为什么每次分配完毕，需要清除原始队列 que.push(p); p = q; } } } //一趟的分配收集完毕，最后要清空十个队列 for (int i = 0; i < 10; i++) { arr[i]->clear(); } //进行下一趟的分配和收集 d *= 10; } //输出队列中排好序的元素 print(que); 链式基数排序的时间复杂度和空间复杂度分析 假设：n —— 记录数 ， d —— 关键字数， rd —— 关键字取值范围（如十进制为10） 分配（每趟）：T(n)=O(n) ，每次分配，分配的都是所有的关键字，故是 n 收集（每趟）：T(n)=O(rd) ，收集的是桶里的数据，也就是关键字的取值范围大小rd，是桶的数目 总的时间复杂度：因为一次完整的排序是分配+收集，也就是 n+rd ，而一共需要的排序趟数，恰恰就是关键字的数目 d，故T(n)=O(d(n+rd)) 空间复杂度：S(n)=2rd 个队列指针 + n 个指针域空间，因为一个桶本质是一个链式队列，一共 rd 个桶，每个队列有队头和队尾两个指针，就是2rd 个队列指针。又原来的代拍序列是一个单链表，那么自然需要 n 个next指针控件。
展开
