13.7 排序

优质
小牛编辑
135浏览
2023-12-01

既然牌堆中的纸牌顺序已经乱了,我们还是需要一种让纸牌重新有序的方法。讽刺的是,有一个排序算法与洗牌算法很相似。

再一次,我们遍历牌堆,而且在每个位置都选择另一张纸牌并交换。唯一的区别是,这次我们不是随机的选择另一张牌,而是选择剩余牌堆中最小的纸牌。

“剩余牌堆中”指的是以i或i右侧的值为索引的纸牌。

for (int i=0; i<cards.length(); i++) {
  // 在位置i及其右侧找到最小的纸牌
  // 将第i张纸牌与最小的纸牌交换
}

此外,伪代码有助于辅助函数的设计。这种情况下,我们又能使用findLowestCard了,它接收纸牌向量和我们要开始查找的位置的索引值。

使用伪代码指出需要什么辅助函数的过程称为自上而下的设计,它不同于我们在10.8节讨论的下下而上的设计。

我们再次把实现留给读者。