令人惊艳的算法 -- Quick Sort - 未名空间MITBBS历史存档

x*o2014-12-09 08:12

1 楼

快速排序算法
我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
边，然后剩下两堆继续这样整，这样排的快！”
这是我见识过最惊艳的算法使用，没有之一

H*72014-12-09 08:12

2 楼

语文水平不行啊

w*r2014-12-09 08:12

3 楼

数学系毕业的图书管理员

x*y2014-12-09 08:12

4 楼

难道不是计算机系毕业的？

【在 w****r 的大作中提到】

: 数学系毕业的图书管理员

w*r2014-12-09 08:12

5 楼

计算机系的前身是数学系

【在 x**y 的大作中提到】

: 难道不是计算机系毕业的？

G*Y2014-12-09 08:12

6 楼

我试过
未必快
移动成本远大于比较成本
这时候
qs还是最快的吗？

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

h*02014-12-09 08:12

7 楼

这个不是关键，关键是实际操作时要摊一地吗？否则不可能不停分堆的。

们教
另一

【在 G**Y 的大作中提到】

: 我试过
: 未必快
: 移动成本远大于比较成本
: 这时候
: qs还是最快的吗？

G*Y2014-12-09 08:12

8 楼

不用
桌子大点就行

【在 h*****0 的大作中提到】

: 这个不是关键，关键是实际操作时要摊一地吗？否则不可能不停分堆的。
:
: 们教
: 另一

w*a2014-12-09 08:12

9 楼

asymptotically, YES

【在 G**Y 的大作中提到】

: 我试过
: 未必快
: 移动成本远大于比较成本
: 这时候
: qs还是最快的吗？

n*t2014-12-09 08:12

10 楼

有特别多钞票要数的时候，我只数尾号 4 和 8 的，加起来乘 5 基本就对了

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

P*i2014-12-09 08:12

11 楼

这个情境还是interval sort快

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

l*s2014-12-09 08:12

12 楼

实用当然是bucket sort(BS)最快

【在 P****i 的大作中提到】

: 这个情境还是interval sort快

M*P2014-12-09 08:12

13 楼

一看就是想象出来的。实际图书馆的书上都有号的.理科都是Q到T。用眼看排序就能分
成小堆。根本用不着放地上排序。

★ 发自iPhone App: ChineseWeb 7.8

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

c*y2014-12-09 08:12

14 楼

这步已经被大妈用bucket sort做了。志愿者要处理的都是Q打头的书。
大妈冷笑：以为我不懂，我什么没见过？

【在 M*P 的大作中提到】

: 一看就是想象出来的。实际图书馆的书上都有号的.理科都是Q到T。用眼看排序就能分
: 成小堆。根本用不着放地上排序。
:
: ★ 发自iPhone App: ChineseWeb 7.8

m*02014-12-09 08:12

15 楼

快不快取决于数列特性

【在 G**Y 的大作中提到】

: 我试过
: 未必快
: 移动成本远大于比较成本
: 这时候
: qs还是最快的吗？

g*o2014-12-09 08:12

16 楼

人手多，就并行的快
一个人，偶看还是按书号查找插入快，因为书号一眼就看到哪个最接近了，比二分查找
的效率还高

n*g2014-12-09 08:12

17 楼

o(∩_∩)o...要害死他们

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

t*42014-12-09 08:12

18 楼

每次都刚好抽到最小或最大号，杯具了

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

w*r2014-12-09 08:12

19 楼

估计要数附图那么多钱，误差才不会太大。。。

【在 n*****t 的大作中提到】

: 有特别多钞票要数的时候，我只数尾号 4 和 8 的，加起来乘 5 基本就对了

c*n2014-12-09 08:12

20 楼

这不也要一张张的看过去吗？

【在 n*****t 的大作中提到】

: 有特别多钞票要数的时候，我只数尾号 4 和 8 的，加起来乘 5 基本就对了

i*h2014-12-09 08:12

21 楼

难道不是秤一下最快

【在 w**********r 的大作中提到】

: 估计要数附图那么多钱，误差才不会太大。。。

R*a2014-12-09 08:12

22 楼

混板砖进去了怎么办

【在 i***h 的大作中提到】

: 难道不是秤一下最快

P*H2014-12-09 08:12

23 楼

难道不是插入更好？。快排还要递归，要大桌子。

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

R*a2014-12-09 08:12

24 楼

书多的时候插入每次找到正确位置比较慢

【在 P**H 的大作中提到】

: 难道不是插入更好？。快排还要递归，要大桌子。

P*H2014-12-09 08:12

25 楼

log n

【在 R***a 的大作中提到】

: 书多的时候插入每次找到正确位置比较慢

b*n2014-12-09 08:12

26 楼

好煞笔的应用
搬书多费体力，找位置就是眼睛扫几下，做功差了几百倍

P*H2014-12-09 08:12

27 楼

而且书的移动，推一下就行了，操作O(1)。
全部排序可以在原来的书架只能就行了。连额外的桌子都不要。

【在 P**H 的大作中提到】

: log n

E*12014-12-09 08:12

28 楼

递归时间复杂度减小了，但是空间复杂度上去了，得overload logn级的调用，大妈有
这么大地方放来放去吗？

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一

R*a2014-12-09 08:12

29 楼

问题是图书馆重新放书不是就放这一个书架啊，
你不先进行bucket/quick pre-sort，拿起一本书你可能需要上四楼把这本书放下，
然后跑回来，再拿一本书，发现还得再上四楼

【在 P**H 的大作中提到】

: 而且书的移动，推一下就行了，操作O(1)。
: 全部排序可以在原来的书架只能就行了。连额外的桌子都不要。

R*d2014-12-09 08:12

30 楼

你们都是没做过图书管理员的，当年我在大学图书馆当管理员都是把一个架子上的书
直接放上去。

【在 x****o 的大作中提到】

: 快速排序算法
: 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教
: 的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一
: 边，然后剩下两堆继续这样整，这样排的快！”
: 这是我见识过最惊艳的算法使用，没有之一