【Weiss】【第03章】练习3.13:桶排序
2024-09-07 07:07:07
【练习3.13】
利用社会安全号码对学生记录构成的数组排序。编写一个程序进行这件工作,使用具有1000个桶的基数排序并且分三趟进行。
Answer:
首先,对社会安全号码不了解的就把它当成一个不超过9位的正整数就好了。
于是题目就是,通过1000个桶,对9位正整数进行桶排序。
因为一次最多比较三位(1000桶),刚好分三趟进行,加上最后复制回数组的一次,共遍历数组长度四次,时间复杂度O(N)
测试代码:
#include <iostream>
#include "linklist.h"
using namespace std;
using namespace linklist;
template class List<int>;
int main(void)
{
int numbers[] = { , , , , , , , , , };
bucketsort(numbers, );
for (auto elem : numbers)
cout << elem << endl; system("pause");
}
实现代码:
//练习3.13新增,4位数桶对不超过9位的正整数(社会安全号)桶排序
void bucketsort(int ssn[], int size)
{
//每次对三位数进行排序
List<int>* lastthree = new List<int>[]; //初次排序时,遍历数组
//将每个元素后三位压入与之对应编号的链表
for (int i = ; i != size; ++i)
lastthree[ssn[i] % ].additem(ssn[i]); //以后的排序时,按顺序遍历前一个链表
//将元素的某三位压入与之对应编号的链表
List<int>* midthree = new List<int>[];
for (int i = ; i != ; ++i)
{
for (Node<int>* iter = lastthree[i].begin(); iter != nullptr; iter = iter->next)
midthree[(iter->data / ) % ].additem(iter->data);
}
delete[] lastthree;
List<int>* firstthree = new List<int>[];
for (int i = ; i != ; ++i)
{
for (Node<int>* iter = midthree[i].begin(); iter != nullptr; iter = iter->next)
lastthree[iter->data / ].additem(iter->data);
}
delete[] midthree; //排序完成后,按顺序遍历当前链表,并将元素依次复制入原数组
for (int i = , j = ; i != ; ++i)
{
for (Node<int>* iter = lastthree[i].begin(); iter != nullptr; iter = iter->next)
ssn[j++] = iter->data;
}
delete[] lastthree;
}
最新文章
- BWT压缩算法(Burrows-Wheeler Transform)
- Java IO6:字符流进阶及BufferedWriter、BufferedReader
- java并发:简单面试问题集锦
- oracle sqlplus存储过程控制台输出信息
- bee使用
- The Beatles-Hey Jude
- Python12期培训班-day1-三级菜单代码分享
- hdu 5755(高斯消元——模线性方程组模板)
- C语言获取系统时间的几种方式[转]
- 批处理:遍历输出指定后缀格式的文件名.bat
- 构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统(17)-LinQ动态排序
- Event | Beijing Makerspace
- 32位Windows7
- 【Android Developers Training】 95. 创建一个同步适配器
- 深入理解Java 虚拟机阅读笔记(一)
- MongoDB基本shell操作
- C#抓取和分析网页的类
- 浅谈IM(InstantMessaging) 即时通讯/实时传讯
- dbf,Idx 文件格式
- ribbon的注解使用报错--No instances available for [IP]