算法设计与分析 第2次作业
算法设计与分析 第2次作业
各种排序算法的实现与分析
请用任意语言(C/C++/Java/Python等), 实现选择排序、插入排序、快速排序、归并排序。
选择排序:
1 |
插入排序:
1 |
快速排序:
1 |
归并排序:
1 |
问题:
- 生成不同规模、不同分布的测试数据, 对比测试上述4种代码的运行表现。
(要求数据规模至少包括1万、10万、100万, 分布要求必须包含一定范围内的随机数据。下表仅写排序运行时间, 不要包括读入数据的时间。)
答: (至少包含以下内容, 推荐对是否有重复元素附加测试)
| 选择排序 | 插入排序 | 快速排序 | 归并排序 | |
|---|---|---|---|---|
| 1万正序 | ||||
| 1万逆序 | ||||
| 1万随机 | ||||
| 10万正序 | ||||
| 10万逆序 | ||||
| 10万随机 | ||||
| 100万正序 | ||||
| 100万逆序 | ||||
| 100万随机 |
附: 各规模随机数的说明
1万随机: (应至少包括范围, 是否有重复元素, 分布: 均匀分布即可)
10万随机: (应至少包括范围, 是否有重复元素, 分布: 均匀分布即可)
100万随机: (应至少包括范围, 是否有重复元素, 分布: 均匀分布即可)
生成随机数据的方法: (以10万规模随机数为例)
1 |
- 实际的排序问题输入, 元素可能有重复, 如果输入中有较多重复元素, 如何改进快速排序, 使划分效率更高？请写出改进后的核心代码或算法
答:
