V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
chanlion
V2EX  ›  算法

你还记得当年大学学的 Quicksort 吗?

  •  
  •   chanlion · 2017-11-27 16:15:50 +08:00 · 2984 次点击
    这是一个创建于 2313 天前的主题,其中的信息可能已经有所发展或是发生改变。

    周末复习了一下快速排序算法,从 wikipedia 和算法书上了解到与快速排序的多个方面,写成了一篇小短文作为笔记。现在给大家分享一下 :)

    以下是一些历史描述:

    Tony Hoare 在 1959 年做一个机器文本翻译工作时,需要一个排序算法使得在查字典前将所有的文本都排好序,然后直接查字典就行了。开始他尝试使用插入排序,结果太慢了,然后很快就想到了新算法—— Quicksort。等他做完这个项目回到英国时,他的老板跟他打赌 10 便士说“你这个算法肯定没有 shellsort 快”,可想而知,Hoare 赢了。其后再 Hoare 学习了 ALGOL 语言之后,他能够使用递归将他的快速排序算法发表在当时的顶尖计算机科学杂志上。因而,也获得了 1980 的图灵奖。

    除此之外还简单介绍了算法过程,以及多个实现版本(以及它们之间的争论)。考虑到如何选取轴点和如何处理大量相当元素以及已经排好序的输入序列处理,有多个优化方案我都一一过了一遍。

    写完之后的一个感受就是写的过程其实更加加深了对所学内容的理解。这正是我一直在做的事情,我把读过的书和理解过的知识自己整理出来。这是一项长期而系统工作,且期待若干年后会怎样。

    博客的地址在此: http://mrlongx.com/index.php/2017/11/26/quicksort/

    3 条回复    2017-12-27 17:14:14 +08:00
    lybtongji
        1
    lybtongji  
       2017-11-27 19:01:46 +08:00
    中学到现在还记得
    hackpro
        2
    hackpro  
       2017-11-27 21:28:22 +08:00 via iPhone
    好文 其实快排从分治的角度还是很好理解的
    arzterk
        3
    arzterk  
       2017-12-27 17:14:14 +08:00
    C 里面最简单的是那个查找表排序,很符合人类习惯;
    ps,快排用 haskell 写也很容易理解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1354 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:42 · PVG 01:42 · LAX 10:42 · JFK 13:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.