使用有限的操作对双端队列进行排序?

纳夫琳·辛格(Navleen Singh)

嗨,我在Robert Sedgewick的Algorithms 4th Edition中遇到了一个问题。

出队排序。说明如何对一副纸牌进行排序,限制条件是,唯一允许的操作是查看前两张纸牌的值,交换前两张纸牌以及将顶卡移到纸牌底部。

我真希望有人能解释如何做到这一点,我真的迷失了。谢谢

templatetypedef

与其想到卡片组有顶部和底部,不如想象一下卡片组是成环排列的。您可以想象在两个特定的卡之间放置一个标记,该标记然后对应于牌组的顶部。然后,您“交换前两张卡”的操作将两张卡交换到标记的左侧,而“将卡座的顶部移动到底部”的操作对应于将标记向左移动一个步骤。

有了这个,您自然可以适应气泡排序以在此设置中工作。永久标记环中的一个位置作为起点。然后,重复执行以下操作:如果标记左侧的两张卡顺序混乱,请交换它们。然后,将标记向左移动一步。作为规则的一个例外,如果标记比标记的初始位置早一步,则不要进行比较。如果您不做任何交换就绕圈转,那就完成了!

用伪代码显示如下:

repeat the following until no swaps are made:
    counting from i = 1 to n - 1, inclusive:
       if the top two cards are out of order, swap them.
       move the top card of the deck to the bottom.
    then, move the top card of the deck to the bottom.

希望这可以帮助!

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

有限大小的FIFO(双端队列)

使用有限的堆栈操作进行排序

使用最大API进行双端队列?

如何使用双端队列进行线程通信?

使用有限的并行性对Scala Future进行排序(无需弄乱ExecutorContext)

是否可以使用这组非常有限的运算符对整数进行排序?

显示c = | a-b | 有限地使用有限的操作

如何使用C#互操作对Excel中的列进行重新排序

如何仅使用python中的堆栈操作对堆栈进行排序?

Python:具有双端队列样式排序的collections.Counter

RDD操作对pyspark中的值进行排序

使用有限的工具在客户端之间同步数据(无网络套接字,线程数有限)

如何使用堆栈反转双端队列?

如何使用双端队列而不是在MongoDB中查找进行多次更新?

php从表中选择数量有限的数据,并按日期排序以进行延迟加载

具有有限队列的Java线程池

双端队列的容量

查看双端队列

检测双精度数是否有限的最快方法?

双端队列,其中所有推入/弹出(前/后)和get_min()均为O(1)操作

使用github操作对Firebase进行部署部署

实例没有属性-双端队列库

在线程中拥有Queue的双端队列

如何使用 typescript/javascript 从对象数组中操作有限的对象

如何在laravel中检索有限数量的相关模型并按相关模型对集合进行排序?

如何对结果数量有限的IEnumerable进行排序?(.OrderBy.Take的另一个实现)

为什么使用双端队列代替内置的Stack <>?

使用双端队列的滑动窗口(运行时错误)

我是否以线程安全的方式使用此双端队列?