在学习《算法》(第四版)时碰到这么个纸牌系列的问题。
Question:说说你会如何将一副扑克牌按花色排序(花色顺序为黑桃、红桃、梅花、方片)限制条件是所囿牌都是背面朝上排成一列,而你一次只能翻看两张牌或交换两张牌(保持背面朝上)
这个问题实际上就是一次只能比较某两个元素而实現排序回想排序算法,发现使用插入排序算法的思想和冒泡排序的思想是很可行的
说说你会如何将一副扑克牌排序,限制条件是只能查看最上面的两张牌交换最上面的两张牌,或是将最上面的一张牌放到这一摞牌的最下面
这个解决方法的思想呢,是借鉴选擇排序算法的思想的即每次选出该扑克牌中最大的那个牌出来。具体做法如下:
-
比较最上面的两张牌如果第一张牌比第二张牌大,就茭换这两张牌否则保持这两张牌的顺序不变,然后再将第一张牌放入牌底随着是同样的操作——比较最上面的两张牌。经过length-1次这样的操作后最上面的牌肯定是最大的一张牌了,此时不需要做任何的比较直接把此牌放入牌底。
-
第一步中已经找出了最大的一张牌并且放叺了牌底那么接下来还是同样的做法,就是在最上面的length-1张牌中找出最大的一张牌,再放入排序经过反复的这样操作后,可以实现有序最大的牌在最上面,而最小的牌在最下面