以图明志

计算机算法

[专题] 快速排序里的学问:随机化快排

选择随机数作为枢纽元
一般来说随机选取枢纽元这种策略非常安全,除非随机数生成器有问题(这不像你所想象的那么罕见),因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。算法与前面《算法导论》里的例子差不多,只是在调用分割Partition时加入一个随机数,具体可以参看程序。

计算机算法

[专题] 快速排序里的学问:枢纽元选择与算法效率

枢纽元选择也有学问
通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。如果输入是随机的,那么这是可以接受的,但是如果输入是预排序的或者是反序的,那么这样的枢纽元就产生一个劣质的分割,因为所有的元素不是被划入S1就是被划入S2。更有甚者,这种情况发生在所有的递归调用中。

计算机算法

[专题] 快速排序里的学问:霍尔快排的实现

霍尔快排的C语言实现
专题的前一篇讲了快速排序的始祖——霍尔快排,那么这里就简单地实现以下霍尔快排。补充说明下,快排的一个核心步骤是选取枢纽元,通常的做法是将第一个元素用作枢纽元,《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。排序的思路是,选定一个枢纽元,比枢纽元大的全部丢到右边,比枢纽元小的全部丢到左边。
1 / 1 首页 < Prev 1 Next > 尾页 页码: