algorithm - 快速选择算法 - 简化说明

Question

我之前问过这个HERE ，但是我希望进一步简化对快速选择(基于快速排序)的解释。我问的上一个问题包括一些示例代码(所以你知道我在说什么)。

我想知道是否有人在任何时候任何地方都将快速选择的规则和指南总结为一种游戏，人们可以通过遵循易于理解的规则来了解算法的工作原理，这些规则可以应用于比方说一副纸牌或数字在纸片上。

我认为快速选择算法的简化解释对我理解它的工作原理至关重要，因为我收到的教程和解释仍然难以理解和形象化。甚至 youtube 上将快速排序变成舞蹈的视频也没有太大帮助。

在此先感谢 Stack，到目前为止，您提供了很大的帮助。

Answer 1

您走进一个有 200 名 child 的体育馆。今天是 9 月 8 日，所以您迫切希望找到第 98 个最矮的 child 。你知道你可以把它们从最矮到最高排成一排，但这会花很长时间。 “我知道”，你想，“我可以使用 QUICKSELECT!”

你走到人群中，闭上眼睛，伸出手指，转了三圈。当您睁开眼睛时，您正直指着其中一个 child Peter Pivot。你说，“快!所有比彼得矮的人都站过来。所有比彼得高的人都站那边。如果你和彼得一样高，你可以分到任何一组。”

children 扭来扭去，很快就站成两组了。你数了数，发现矮个子组有 120 个 child ，个子较高的组有 79 个 child 。您知道第 98 个最矮的 child 必须在较矮的一组中，所以您告诉彼得和 79 个较高的 child 坐在看台上。

你再次闭上眼睛，伸出手指，转了三圈。当你睁开眼睛时，你正直指着彼得的妹妹保拉·皮沃特。你说:“快点!你们中那些还站着的人。如果你比宝拉矮，就站过来。如果你比宝拉高，就站那边。如果你和宝拉一样高，你可以进入任何一组。”

children 扭来扭去，很快就站成两组了。你数了数，发现矮个子组有 59 个 child ，个子较高的组有 60 个 child 。您知道第 98 个最矮的 child 一定在较高的组中，所以您告诉 Paula 和 59 个较矮的 child 坐在看台上。

你再次闭上眼睛，伸出手指，转了三圈。当你睁开眼睛时，你正直指宝拉的表妹普鲁登斯·皮沃特。你说:“快点!你们中那些还站着的人。如果你比普鲁登斯矮，就站过来。如果你比普鲁登斯高，就站那边。如果你和普鲁登斯一样高，你可以进入任何一组。”

children 扭来扭去，很快就站成两组了。你数了数，发现矮个子组有 37 个 child ，个子较高的组有 22 个 child 。你知道 Paula 和其他 59 个矮小的 child 正坐在看台上。加上仍然站着的 37 个较矮的 child ，您知道共有 97 个 child 比 Prudence 矮。因此，Prudence 是第 98 个最矮的 child !

快速选择 FTW!