x****o 发帖数: 21566 | 1 快速排序算法
我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教
的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一
边,然后剩下两堆继续这样整,这样排的快!”
这是我见识过最惊艳的算法使用,没有之一 |
H******7 发帖数: 34403 | |
w****r 发帖数: 15252 | |
x**y 发帖数: 644 | 4 难道不是计算机系毕业的?
【在 w****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 数学系毕业的图书管理员
|
w****r 发帖数: 15252 | 5 计算机系的前身是数学系
【在 x**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是计算机系毕业的?
|
G**Y 发帖数: 33224 | 6 我试过
未必快
移动成本远大于比较成本
这时候
qs还是最快的吗?
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
h*****0 发帖数: 4889 | 7 这个不是关键,关键是实际操作时要摊一地吗?否则不可能不停分堆的。
们教
另一
【在 G**Y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我试过 : 未必快 : 移动成本远大于比较成本 : 这时候 : qs还是最快的吗?
|
G**Y 发帖数: 33224 | 8 不用
桌子大点就行
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不是关键,关键是实际操作时要摊一地吗?否则不可能不停分堆的。 : : 们教 : 另一
|
w*********a 发帖数: 9279 | 9 asymptotically, YES
【在 G**Y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我试过 : 未必快 : 移动成本远大于比较成本 : 这时候 : qs还是最快的吗?
|
n*****t 发帖数: 22014 | 10 有特别多钞票要数的时候,我只数尾号 4 和 8 的,加起来乘 5 基本就对了
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
|
|
P****i 发帖数: 1362 | 11 这个情境还是interval sort快
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
l*******s 发帖数: 7316 | 12 实用当然是bucket sort(BS)最快
【在 P****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个情境还是interval sort快
|
M*P 发帖数: 6456 | 13 一看就是想象出来的。实际图书馆的书上都有号的.理科都是Q到T。用眼看排序就能分
成小堆。根本用不着放地上排序。
★ 发自iPhone App: ChineseWeb 7.8
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
c*****y 发帖数: 542 | 14 这步已经被大妈用bucket sort做了。志愿者要处理的都是Q打头的书。
大妈冷笑:以为我不懂,我什么没见过?
【在 M*P 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一看就是想象出来的。实际图书馆的书上都有号的.理科都是Q到T。用眼看排序就能分 : 成小堆。根本用不着放地上排序。 : : ★ 发自iPhone App: ChineseWeb 7.8
|
m**********0 发帖数: 737 | 15 快不快取决于数列特性
【在 G**Y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我试过 : 未必快 : 移动成本远大于比较成本 : 这时候 : qs还是最快的吗?
|
g*****o 发帖数: 5955 | 16 人手多,就并行的快
一个人,偶看还是按书号查找插入快,因为书号一眼就看到哪个最接近了,比二分查找
的效率还高 |
n****g 发帖数: 14743 | 17 o(∩_∩)o...要害死他们
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
t****4 发帖数: 7500 | 18 每次都刚好抽到最小或最大号,杯具了
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
w**********r 发帖数: 986 | 19 估计要数附图那么多钱,误差才不会太大。。。
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有特别多钞票要数的时候,我只数尾号 4 和 8 的,加起来乘 5 基本就对了
|
c****n 发帖数: 1646 | 20 这不也要一张张的看过去吗?
【在 n*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有特别多钞票要数的时候,我只数尾号 4 和 8 的,加起来乘 5 基本就对了
|
|
|
i***h 发帖数: 12655 | 21 难道不是秤一下最快
【在 w**********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计要数附图那么多钱,误差才不会太大。。。
|
R***a 发帖数: 41892 | 22 混板砖进去了怎么办
【在 i***h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是秤一下最快
|
P**H 发帖数: 1897 | 23 难道不是插入更好?。快排还要递归,要大桌子。
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
R***a 发帖数: 41892 | 24 书多的时候插入每次找到正确位置比较慢
【在 P**H 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是插入更好?。快排还要递归,要大桌子。
|
P**H 发帖数: 1897 | 25 log n
【在 R***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 书多的时候插入每次找到正确位置比较慢
|
b*****n 发帖数: 17570 | 26 好煞笔的应用
搬书多费体力,找位置就是眼睛扫几下,做功差了几百倍 |
P**H 发帖数: 1897 | 27 而且书的移动,推一下就行了,操作O(1)。
全部排序可以在原来的书架只能就行了。连额外的桌子都不要。
【在 P**H 的大作中提到】![](/moin_static193/solenoid/img/up.png) : log n
|
E*******1 发帖数: 3464 | 28 递归时间复杂度减小了,但是空间复杂度上去了,得overload logn级的调用,大妈有
这么大地方放来放去吗?
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|
R***a 发帖数: 41892 | 29 问题是图书馆重新放书不是就放这一个书架啊,
你不先进行bucket/quick pre-sort,拿起一本书你可能需要上四楼把这本书放下,
然后跑回来,再拿一本书,发现还得再上四楼
【在 P**H 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 而且书的移动,推一下就行了,操作O(1)。 : 全部排序可以在原来的书架只能就行了。连额外的桌子都不要。
|
R******d 发帖数: 5739 | 30 你们都是没做过图书管理员的, 当年我在大学图书馆当管理员都是把一个架子上的书
直接放上去。
【在 x****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 快速排序算法 : 我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架,管理员大妈给他们教 : 的时候说:“你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一 : 边,然后剩下两堆继续这样整,这样排的快!” : 这是我见识过最惊艳的算法使用,没有之一
|