我正在尝试为以下排序问题找到最佳算法。
在带有一个过道的礼堂中，有 N = K×M 个席位，每个过道有 K 行，并且 M 个席位。假定 K 比 M 大，但我认为这并不重要。内有 N 个人
与座位(分配的座位)的双射。假设人们没有
像等待，排队的最快捷方式是什么
尽快坐在他们的座位上？
我运行了一些简单的实验(使用随机排列)，
似乎让他们随机排队要比让他们随机排队要快
前排第三(沿过道向下)的人首先排好队，然后
中间三分之一，然后是后三分之一。对我来说这似乎是错误的。
如果这很重要，我将在MatLab中编写。有什么想法或答案吗？
最佳答案
巴赫马特(Bachmat)，贝伦德(Berend)，萨皮尔(Sapir)，斯基埃纳(Skiena)和斯托利亚洛夫(Stolyarov)的一篇很好的文章名为Analysis of airplane boarding via space-time geometry and random matrix theory，它为飞机登机这一确切问题建模。从他们的摘要:
本文的结论是:
对于您的设置，我认为这意味着您应该忽略人们在走道处有多远，而应关注他们离过道有多远。该模型还考虑了存放行李的时间，因此您可能需要根据实际情况进行一些调整。无论如何，我认为这可以证实您在模型中找到的内容。
关于algorithm - 最好的预留座位排序算法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5317135/