一道 10 年前面试问到的算法题

[abc0def]

最近发现自己很久之前在知乎提问过一个算法问题:

如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。

这个问题是 10 年前在我面试腾讯微信 NLP 组实习岗位时被问到的。由于当时是我第一次实习面试，有点紧张，而且我当时没有问清楚，隐含条件是其实还能知道这副牌的总数，所以没有做出来。当年问的知乎好像没啥答案。最近有想了一下，感觉这题其实挺有意思的，写了一个解题思路

[算法] 在有限制的情况下将一副牌排序

[cloudzhou]

这道题目有意思，mark 一下

[mustcool]

有意思

[chen0520]

不会，等大佬。。。

[abc0def]

@chen0520 哈哈可以看看上面链接，我把自己解题思路写了一下

[NoobPhper]

好像都没变过, 一直都有

[iOCZS]

上面冒泡总会和底部上来的有序部分相遇，这时候冒泡出来的和有序部分合并，再一起回到底部，上面继续冒泡，重复这个过程就完成排序了。

[InDom]

怎么感觉是冒泡啊?

[MoYi123]

https://zh.wikipedia.org/wiki/%E7%BD%AE%E6%8D%A2%E7%9A%84%E5%A5%87%E5%81%B6%E6%80%A7

根据这个原理, 可以保证一定可行.

[newtype0092]

暂时想不到其他的办法，看起来就是冒泡。。。

对扑克牌这种数据连续的场景，因为当前要找的第 i 小的牌是已知的，如果遇到了可以直接 break ，算是个微微优化吧，对时间复杂度没影响就是了。

[sillydaddy]

想了半分钟。这不就是冒泡吗？最上面的 2 张牌就是冒泡算法里面对比大小并交换的 2 张牌。将最上面一张放到底部，就是 index+1 ，比较下 2 张牌。

[forty]

人脑怎么排，写成代码就能实现了，优化是另一层的问题。跟冒泡很像啊。
先不考虑优化，一种很简单的策略来实现：

1. 比较上面 2 张，将大的放到底部去，再比较上面 2 张，又将大的放到底部去，这样重复一轮之后，最小的那张就在最上面了，此时把这个最小的放到底下去。
2. 重复步骤 1 ，找到第二小的了，且此时最小的这 2 张是相邻的，2 张都放到底下去（先小后大）。
3. 一直重复就可以了， 直到最上面变成最小的那张。

逻辑很简单吧。

[sobev]

比较的时候只需要把小牌的留在最前面就好了，大的直接往后放，等一轮循环结束，最小的牌就在最前面。
下次循环 index+1

[q727729853]

@forty 你重复步骤 1 的时候，最小的两张就不可能相连了。。你已经放了个大的到底部了。。。

[hackhu2019]

基于选择排序，我们每次取两张牌，把最小的牌留着，大的牌放排底，重复一轮，最小的牌就在最上面了，再从第二张牌开始重复这个过程

[kkbear]

@hackhu2019 问题是，第二轮开始，你并不能锁定第一轮最小的牌让其不移动

[janwarlen]

@sobev #12 只能查看最上面两张

[wineast]

@kkbear 在第二轮开始前，把第一轮找到的最小牌放到最下面，这样，第二轮结束的时候（这一轮 每次比较都会有一张牌被放到最下面，使得第一轮的那张最小牌被“冒泡”上来），应该是 第二小牌，第一小牌，其他牌 这个顺序

[vgbhfive]

@hackhu2019 第一轮排序完后，最小的牌在最前面，在开始第二轮之前，把最小的牌挪到最后面，然后再继续比较第一张和第二张，此时第二张的取值范围就是[0, n-2]。

[dinghmcn]

@q727729853 #13 第二轮完成，上面两张就是最小的两张，因为你要把 N-2 放到下面会把最小的顶上来；第 N 轮完成前 N 张就是最小的 N 张；逻辑没有问题，本质就是冒泡。

[iOCZS]

一叠纸牌从上到下分为冒泡区，有序区，无序区。冒泡区保证最小的在在顶部，冒泡区淘汰的进入无序区，最终冒泡区的大小会变为 1 ，和有序区相遇，并融入其中。这时候再把有序区整体搬到底部。就变成新的冒泡区，有序区，空的无序区。

[fayeeeeee]

这个是不是厄斐琉斯的控刀啊

[leonshaw]

反过来把牌堆看作不动，等价于在每次数组中读取指针当前和下一个元素，选择对调与否，然后指针后移（尾部折返）。

[vance123]

归纳法吗

[iEverX]

https://gist.github.com/iEverX/919935272d6db1e31665a3c197f5b7d1

试了一下，和 lz 的思路是一致

[iwdmb]

惊讶 ChatGPT 的实力...

[abc0def]

@iwdmb 算法题对于 chatgpt 来说都太简单了

[milkpuff]

写了一个好像可以实现

[forty]

@q727729853 “@forty 你重复步骤 1 的时候，最小的两张就不可能相连了。。你已经放了个大的到底部了。。。”
并不会。
我再解释一下吧。
假设 54 张牌，目标是排成这样的顺序：黑桃 A, 黑桃 2, 黑桃 3……
第 1 轮，达成牌堆：******,黑桃 A 。
第 2 轮，先达成牌堆：黑桃 2******黑桃 A******。不停，保持黑桃 2 在最上，把其它牌换到底下去。直到黑桃 2 下面就是黑桃 A ，最小的 2 张就相邻了。再做 3 步操作，达成牌堆：******,黑桃 A,黑桃 2 。
第 3 轮，达成牌堆：******,黑桃 A, 黑桃 2, 黑桃 3 。
以此类推。

这样能理解吗？

[smdbh]

不是大的放上面，然后在放最底下。 如果 n 次不交换，排序完成？