Quickselect算法-简化说明

Question

在HERE之前我已经问过这个问题，但是我希望对quickselect (基于quicksort)的解释有进一步的简化。我之前问的问题包括一些示例代码(这样您就知道我在说什么了)。

我想知道是否有人在任何时候总结了quickselect的规则和指导方针，在游戏中，人们可以通过遵循容易理解的规则来学习算法是如何工作的，这些规则可以应用于纸牌或纸片上的数字。

我认为对快速选择算法的简单解释对我理解它的工作原理是至关重要的，因为我收到的教程和解释仍然很难掌握和可视化。即使是youtube上那些把快速排序变成一种舞蹈的视频也没有多大帮助。

感谢advance Stack，到目前为止你已经帮了很大的忙。

Answer 1

你走进一个有200个孩子的体育馆。今天是9月8日，所以你有一种强烈的愿望，想要找到排名第98位的最矮的孩子。你知道你可以把它们从最短到最高排成一行，但这将永远花费时间。“我知道”，你会想，“我可以使用QUICKSELECT!”

你走到人群中，闭上眼睛，伸出手指，旋转三圈。当你睁开眼睛的时候，你正指着其中一个孩子，Peter Pivot。你说：“快！个子比彼得矮的人，过来站在这里。个子比彼得高的人，站到那边去。如果你和彼得一样高，你可以分到任何一组。”

孩子们拖着脚步走来走去，很快他们就站在两组里了。你数了数，发现矮个子组有120个孩子，高个子组有79个孩子。你知道第98个最矮的孩子一定是矮个子的，所以你告诉彼得和79个高一点的孩子坐在看台上。

你再次闭上眼睛，伸出手指，旋转三圈。当你睁开眼睛时，你正指着彼得的妹妹宝拉·皮沃特。你说：“快！那些还站着的人。如果你们比Paula矮，就站到这边来。如果你们比Paula高，就站到那边去。如果你们一样高，你们可以分到任何一组。”

孩子们拖着脚步走来走去，很快他们就站在两组里了。你数了数，发现矮个子组有59个孩子，高个子组有60个孩子。你知道第98个最矮的孩子一定是高个子组的，所以你告诉Paula和那59个矮孩子坐在看台上。

你再次闭上眼睛，伸出手指，旋转三圈。当你睁开眼睛的时候，你正指着宝拉的表妹，普鲁登斯·皮沃特。你们说：“快！那些还站着的人。如果你们比Prudence矮，就站到这边来。如果你们比Prudence高，就站到那边去。如果你们一样高，你们可以分到任何一组。”

孩子们拖着脚步走来走去，很快他们就站在两组里了。你数了数，发现矮个组有37个孩子，高个组有22个孩子。你知道宝拉和其他59个矮小的孩子正坐在看台上。连同仍然站着的37个矮小的孩子一起，你知道总共有97个孩子比Prudence矮。因此，Prudence是第98位最矮的孩子！

快速选择FTW！