爸爸的分段快速排序法vs妈妈的选择排序法哪个快？
今天比较了下排序算法发现在排序数量小于1000的时候选择排序比快速排序更快一些，搜索了一下发现了一篇非常有意思的文章：
http://xianglichina.spaces.live.com/blog/cns!FAE1D75D1CAE3283!445.entry
爸爸的分段快速排序法vs妈妈的选择排序法
这两天复习了一下内排序和外排序算法，Idea没有找到，倒是意味让我想起了爸爸。
上初中的时候爸妈的学校还没有电脑，每次考完试他们照旧都要根据成绩高低给学生们排个名单出来，自然这样的苦差也成了我的份内事！偶一般都得给他们帮忙。
妈妈处理成绩单的办法很简单：挨次找成绩最高的同学，拎出来，再找剩下的里面成绩最高的同学，拎出来。。。。。。多么简洁的算法 :)
爸爸不这样处理成绩单，他的办法有点特别：先把成绩按照0-10，11-20，21-30 。。。91-100分成10档；接下来把名单按照成绩的档次誊写到10个不同的地方；最后挨次排好每一档里面的顺序就好了！
爸爸每次都要嘲笑妈妈笨，通过亲身的体验我也明显觉得爸爸的办法要快，但是说不出来原因。今天竟然猛然醒悟，老爸确实有高明之处！
原因在于，
1.妈妈地办法是一个典型的内排序的选择排序法，爸爸的办法可以认为是一个类似快排序的算法。设待排序记录为N，一般认为妈妈的办法的时间复杂度为O(N 的平方)；2001年11月《小型微型计算机系统》22卷11期有篇文章证明了，爸爸的办法的时间复杂度近似于O(N)，比快排序的复杂度还要优。
2.爸爸的算法可以扩展到外存排序上面，在多路归并排序多于两趟的情况下，通过抽样统计的分段排序算法甚至好于常用的外存归并排序。
Amazing，这正是我这几天跟老板提的改进外排序算法的基本思想之一！我的想法爸爸当年就已经想到了！汗，爸爸的智慧竟然领先我10年左右！以前竟然没有发现，罪过！！
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
儿子眼中的老子（转载）
7岁：“爸爸真了不起，什么都懂！”
14岁：“好像有时候觉得也不对……”
20岁：“爸爸有点落伍了，他的理论和时代格格不入。”
25岁：“‘老头子’一无所知，毫无疑问，陈腐不堪。”
35岁：“如果爸爸当年像我这样老练，他今天肯定是个百万富翁了。”
……”
45岁：“我不知道是否该和‘老头’商量商量，或许他能帮我出出主意……”
55岁：“真可惜，爸爸去世了，说实在活，他的看法相当高明。”
60岁：“可怜的爸爸，您简直是位无所不知的学者，遗憾的是我了解您太晚了！”
14岁：“好像有时候觉得也不对……”
20岁：“爸爸有点落伍了，他的理论和时代格格不入。”
25岁：“‘老头子’一无所知，毫无疑问，陈腐不堪。”
35岁：“如果爸爸当年像我这样老练，他今天肯定是个百万富翁了。”
……”
45岁：“我不知道是否该和‘老头’商量商量，或许他能帮我出出主意……”
55岁：“真可惜，爸爸去世了，说实在活，他的看法相当高明。”
60岁：“可怜的爸爸，您简直是位无所不知的学者，遗憾的是我了解您太晚了！”
Add a reaction