啃算法
题目
出列排序。说说你会如何将一副扑克牌排序（花色顺序是黑桃、红桃、梅花和方片），限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。
分析
以冒泡排序的思路处理，但是由于只能看两张牌，所以在排序过程中是无法判定排序是否提前完成。
// 伪代码
N = 52 // 总牌数
S = 0 // 已经排序整齐的牌数
for (1 到 N -1) {
// 做 N - 1 轮排序，每轮排序都能找到一张最小牌
for (1 到 N) {
// 每轮 N 次交换或移动
if (前两张牌都是未排列整齐的牌) {
比较后将大的放到最下面（在未排列整齐的牌里找小牌）
if (一旦前两张牌中出现排列整齐的牌) {
比较后将小的牌放到最下面
}
}
}
将最上面的一张牌放到最后
排序完成
我们假设只有 5 张牌，来看看具体会变成什么样子。
初始顺序 -> 4 2 5 3 1
第1轮排序
比较并移动大牌 -> 2 5 3 1 4
比较并移动大牌 -> 2 3 1 4 5
比较并移动大牌 -> 2 1 4 5 3
比较并移动大牌 -> 1 4 5 3 2 // 此时最上面的牌最小
比较并移动小牌 -> 4 5 3 2 1 // 所以改为比较小牌
第2轮排序
// 太巧合了 0，0 看上去虽然顺了，但实际我们只能看到前两张牌，所以是这样的 4 3 * * *
比较并移动大牌 -> 4 3 2 1 5
比较并移动大牌 -> 3 2 1 5 4
比较并移动大牌 -> 2 1 5 4 3 // 此时最上面的牌第二小
比较并移动小牌 -> 2 5 4 3 1 // 所以改为比较小牌
比较并移动小牌 -> 5 4 3 1 2
第3轮排序
比较并移动大牌 -> 4 3 1 2 5
比较并移动大牌 -> 3 1 2 5 4 // 此时最上面的牌第三小
比较并移动小牌 -> 3 2 5 4 1 // 所以改为比较小牌
比较并移动小牌 -> 3 5 4 1 2
比较并移动小牌 -> 5 4 1 2 3
...
每次第 n 轮结束时，牌堆最后 n 张牌都是从小到大排序整齐的了。
所以在 n - 1轮结束时，牌堆最上面的一张牌是最大的牌，其余 n - 1 张牌都是从小大排序整齐的，直接将最上面的牌放到最下面排序就完成了。
第3轮排序结束时 -> 5 4 1 2 3
第4轮排序
比较并移动大牌 -> 4 1 2 3 5 // 此时最上面的牌第四小
比较并移动小牌 -> 4 2 3 5 1 // 所以改为比较小牌
比较并移动小牌 -> 4 3 5 1 2
比较并移动小牌 -> 4 5 1 2 3
比较并移动小牌 -> 5 1 2 3 4
第5轮排序
移动最上面一张 -> 1 2 3 4 5
排序完成
代码
let array = [...] // 牌堆
function less (a, b) {...} // 比较 a 是否小于 b，并返回布尔值
function exch (array, i, j) {...} // 交换 array 中 i 和 j 的值
let N = array.length;
for (let i = 1; i < N - 1; i++) {
for (let j = 0; j < N; j++) {
if (j < (N - 1 - i)) {
if (less(array[0], array[1])) {
exch(array, 0, 1);
}
} else {
if (less(array[1], array[0])) {
exch(array, 0, 1);
}
}
array.push(array.shift());
}
}
array.push(array.shift());
DEMO
罗小黑写写文字
如果喜欢文章 请留下一个赞~
如果喜欢文章 分享给更多人~自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）
转载时请保留原文链接 以保证可及时获取对文章的订正和修改
