这是一个创建于 2551 天前的主题，其中的信息可能已经有所发展或是发生改变。
周末复习了一下快速排序算法，从 wikipedia 和算法书上了解到与快速排序的多个方面，写成了一篇小短文作为笔记。现在给大家分享一下 :)
以下是一些历史描述：
Tony Hoare 在 1959 年做一个机器文本翻译工作时，需要一个排序算法使得在查字典前将所有的文本都排好序，然后直接查字典就行了。开始他尝试使用插入排序，结果太慢了，然后很快就想到了新算法—— Quicksort。等他做完这个项目回到英国时，他的老板跟他打赌 10 便士说“你这个算法肯定没有 shellsort 快”，可想而知，Hoare 赢了。其后再 Hoare 学习了 ALGOL 语言之后，他能够使用递归将他的快速排序算法发表在当时的顶尖计算机科学杂志上。因而，也获得了 1980 的图灵奖。
除此之外还简单介绍了算法过程，以及多个实现版本（以及它们之间的争论）。考虑到如何选取轴点和如何处理大量相当元素以及已经排好序的输入序列处理，有多个优化方案我都一一过了一遍。
写完之后的一个感受就是写的过程其实更加加深了对所学内容的理解。这正是我一直在做的事情，我把读过的书和理解过的知识自己整理出来。这是一项长期而系统工作，且期待若干年后会怎样。
 |
1
lybtongji 2017-11-27 19:01:46 +08:00
中学到现在还记得
|
 |
2
hackpro 2017-11-27 21:28:22 +08:00 via iPhone
好文 其实快排从分治的角度还是很好理解的
|
 |
3
arzterk 2017-12-27 17:14:14 +08:00
C 里面最简单的是那个查找表排序，很符合人类习惯；
ps，快排用 haskell 写也很容易理解 |
Select Language