| 66完成 |
|
|
|
| 代码的录入，运行，代码的阅读笔记 |
|
|
| 三部分快排的比较心得 成功利用了 acm 文件方式进行文件输出结果比较 做了3对cutoff的比较 |
|
| 特别注意 | 作者推荐的 混合型 qsort 4 在这里复杂度 尽然是 最慢的qsort 1的 100倍 | 解决方法： 代码覆盖法阅读解决 |
| 最大领悟 | 代码的美体现在： 不多不少刚刚好！
测试用咧的设计 还有 对 输出的数据 验证， 或者对数据进行统计性的分析 都是花时间的 |
|
|
| 双向确实比 单向的快一倍 | a |
| Todo | 为 qsort 1 增加 对比测试，相当于分 两个分支 （有无最后的swap）。 测试用例：作者在书上说的完全相同的序列 | 难度系数 1 |
|
| 同样的测试用例（如上），对qsort 2用于 少去swap |
|
| todo最重要 | 找到 qsort混合版本 慢的原因
反复读 作者的性能分析（摘要就在本页的图上）
|
|
| 其他 | 时间（从代码角度分析为什么是那个数量级） 继续：找到珠儿上 那些系数的来源（方法：只有请教老师） 寻找一个可行 cutoff寻找方案
|
|
好的测试：是需要！！！！ 分析的。
| 第一种 | 单向划分 |
| 第二种 | 双向划分 |
| 第三种 | 双向划分+ cutoff 分支为insert |
结果小结
2012-4-1 20:21:00
由于输出格式的细节，导致忙乎了一下午。
还有为了寻找一个合适的cutoff, 感觉暂时没有大的发现。（下一次）
| 66 |
| 我的测试结果： 双向快排 时间 比单向 快一倍。
|
| 作者的总结 |
| 图片文字化如下
第一个图片来自于 英文版本
在中文版，作者说到 他的 混合版本排序 性能上接近
系统库（c++）的排序。
|
结果格式说明：
0.000000 1000 in quickSort1
----------------------------------
0.000000 1000 (2) in quickSort2
++++++++++++++++++++
0.000000 1000 (2) in quickSort3 & insert
有数字的三行分别说明了 第一种，第二种，第三种快排的时间和 数组大小
结果附件
0.000000 1000 in quickSort1
----------------------------------
0.000000 1000 (2) in quickSort2
++++++++++++++++++++
0.000000 1000 (2) in quickSort3 & insert
0.000000 1000 in quickSort1
----------------------------------
0.000000 1000 (2) in quickSort2
++++++++++++++++++++
16.000000 1000 (2) in quickSort3 & insert
0.000000 10000 in quickSort1
----------------------------------
0.000000 10000 (2) in quickSort2
++++++++++++++++++++
47.000000 10000 (2) in quickSort3 & insert
0.000000 10000 in quickSort1
----------------------------------
0.000000 10000 (2) in quickSort2
++++++++++++++++++++
31.000000 10000 (2) in quickSort3 & insert
| 66 | 在 为1w个数 排序时， 前两个排序都 不到 ms级别 |
|
| 由于 混合排序数量级不对，此轮忽略 |
63.000000 100000 in quickSort1
----------------------------------
32.000000 100000 (2) in quickSort2
++++++++++++++++++++
2360.000000 100000 (2) in quickSort3 & insert
63.000000 100000 in quickSort1
----------------------------------
31.000000 100000 (2) in quickSort2
++++++++++++++++++++
2344.000000 100000 (2) in quickSort3 & insert
640.000000 1000000 in quickSort1
----------------------------------
375.000000 1000000 (2) in quickSort2
++++++++++++++++++++
96453.000000 1000000 (2) in quickSort3 & insert
640.000000 1000000 in quickSort1
----------------------------------
375.000000 1000000 (2) in quickSort2
++++++++++++++++++++
96438.000000 1000000 (2) in quickSort3 & insert
表格不完全规范版本
| 66 | 尝试寻找最优的cutoff. | 但是未果 |
图：为1w个数 混合排序 的耗时
横坐标是cutoff(步长为2),
竖坐标是 耗时（ms), 感觉 总在两边震荡。
图：为10w个数 混合排序 的耗时
cutoff(步长为5),