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

这道题目有意思，mark 一下

有意思

不会，等大佬。。。

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

好像都没变过, 一直都有

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

怎么感觉是冒泡啊?

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

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

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

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

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

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

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

逻辑很简单吧。

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

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

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

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

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

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

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

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

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

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

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

归纳法吗

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

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

惊讶 ChatGPT 的实力...

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

写了一个好像可以实现

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

这样能理解吗？

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