快速选择算法 - 简化解释

Question

快速选择算法 - 简化解释

algorithmselect

28

我之前在这里询问过类似的问题，但是我希望能进一步简化基于快速排序的quickselect算法的解释。我的上一个问题包含了一些示例代码（这样你就知道我在说什么）。

我想知道是否有人曾经将quickselect的规则和指南总结成一个游戏，通过遵循易于理解的规则来学习算法，比如用纸牌或数字的方式。

我认为对于我理解quickselect算法来说，简化的解释至关重要，因为我现在收到的教程和解释仍然难以掌握和形象化。即使是将快速排序变成舞蹈的YouTube视频也没有太大的帮助。

提前感谢Stack，你们迄今为止真的帮了我很大的忙。

- Edge

“Pivot”的概念，以及在递归过程中如何反复选择它，以及如何因此拆分列表以及如何操作每个子列表。 - Edge

中心点只是您选择的列表中的一个点，用于帮助递归（比如未排序列表中的第一项）。这为您将获得的两个列表半部分提供了随机性，因此更有可能在两个半部分之间获得均匀分布。 - josh shadowfax

你是否熟悉“分治算法原则”？因为快速排序/选择算法就是运用了这个原则。 - Gumbo

我很好奇是否有人把快速排序总结成一款可以用纸牌玩的简单游戏。我在想... 不管怎样，我会再看一下那个原理。 - Edge

你的快速选择算法实际上更为人所知的是二分查找算法。或许这会对你有所帮助。 - Gumbo

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Okasaki · Accepted Answer

你走进一个体育馆，里面有200个孩子。现在是9月8日，你想要找到第98矮的孩子。你知道你可以把他们排成从矮到高的顺序，但那需要很长时间。"我知道了"，你想道，"我可以使用QUICKSELECT算法！"

你混迹于人群中，闭上眼睛，伸出手指，然后转身转了三圈。当你睁开眼睛时，你的手指正好指向其中一个孩子——Peter Pivot。你说："快点！比Peter更矮的人站到这边来，比Peter更高的人站到那边去。如果你和Peter一样高，你可以随便选哪一边。"

孩子们围绕着移动，很快就站成了两组。你数了数发现有120个孩子站在矮的那一边，79个孩子站在高的那一边。你知道第98矮的孩子必须在矮的那一组里，于是你告诉Peter和其他79个孩子坐在看台上。

你再次闭上眼睛，伸出手指，然后转身转了三圈。当你睁开眼睛时，你的手指指向了Peter的妹妹Paula Pivot。你说："快点！还在站着的人，如果你比Paula更矮，就站到这边来。如果你比Paula更高，就站到那边去。如果你和Paula一样高，你可以随便选哪一边。"

孩子们再次围绕着移动，很快又站成了两组。你数了数发现有59个孩子站在矮的那一边，60个孩子站在高的那一边。你知道第98矮的孩子必须在高的那一组里，于是你告诉Paula和其他59个孩子坐在看台上。你再次闭上眼睛，伸出手指，转了三圈。当你睁开眼睛时，你的手指正指向 Paula 的表妹 Prudence Pivot。你说：“快！那些还站着的人，如果你比 Prudence 矮，就过来站这边。如果你比 Prudence 高，就去那边站。如果你和 Prudence 一样高，你可以进入任何一个组。”

孩子们挪动着位置，很快分成两个组。你数了数，发现有37个孩子在矮组，22个孩子在高组。你知道 Paula 和其他59个矮个子孩子坐在看台上。加上仍然站着的37个矮个子孩子，你知道总共有97个孩子比 Prudence 矮。因此，Prudence 是第98矮的孩子！

快速选择胜利！