#算法 第4版# 2.1.14 出列排序 答案

题目

出列排序。说说你会如何将一副扑克牌排序（花色顺序是黑桃、红桃、梅花和方片），限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。

分析

以冒泡排序的思路处理，但是由于只能看两张牌，所以在排序过程中是无法判定排序是否提前完成。

// 伪代码
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

CodePen

罗小黑写写文字

如果喜欢文章 请留下一个赞~
如果喜欢文章 分享给更多人~

在掘金中关注我
在简书中关注我

自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）
转载时请保留原文链接 以保证可及时获取对文章的订正和修改