13.9　练习

本章的示例代码位于仓库 ThinkJavaCode 的目录 ch13 中，有关如何下载这个仓库，请参阅前言中的“使用示例代码”一节。做以下的练习前，建议你先编译并运行本章的示例。

练习13-1

要想更详细地了解本章介绍的排序算法以及其他排序算法，可参阅 http://www.sorting-algorithms.com/。这个网站对这些算法作了诠释，包含演示工作原理的动画，还对这些算法的效率作了分析。

练习13-2

这个练习旨在实现本章介绍的洗牌算法。

(1) 在本书的代码仓库中，有一个名为 Deck.java 的文件，其中包含了本章的示例代码。确认这个文件在你使用的开发环境中能够通过编译。

(2) 在 Deck 类中添加一个名为 randomInt 的方法，让它接受两个 int 参数（low 和 high），并返回一个位于 low 和 high 之间（闭区间）的随机整数。可用 java.util.Random 提供的 nextInt，这个方法在 8.7 节中介绍过。但你应避免每次调用 randomInt 时都创建一个 Random 对象。

(3) 编写一个名为 swapCards 的方法，让它接受两个索引，并互换这两个索引处扑克牌的位置。

(4) 编写一个名为 shuffle 的方法，在其中实现 13.2 节介绍的算法。

练习13-3

这个练习旨在实现本章介绍的排序算法。可用前一个练习中的文件 Deck.java，也可重新创建一个。

(1) 编写一个名为 indexLowest 的方法，让它用方法 compareCard 找出给定范围（从 lowIndex 到 highIndex 的闭区间）内的最小牌。

(2) 编写一个名为 selectionSort 的方法，在其中实现 13.3 节介绍的选择排序算法。

(3) 根据 13.4 节的伪代码编写一个名为 merge 的方法。为对你编写的方法进行测试，最佳的方式是创建一个 Deck 对象，并对其执行洗牌操作，再用 subdeck 将它分成两部分，并用 selectionSort 分别对这两部分进行排序。然后就可将这两部分传递给方法 merge，看看它是否管用。

(4) 编写简单版 mergeSort，即将 Deck 对象分成两部分，用 selectionSort 对这两部分进行排序，再用 merge 创建一个排好序的新 Deck 对象。

(5) 编写递归版 mergeSort。别忘了，selectionSort 是一个非纯方法，而 mergeSort 是一个纯方法，这意味着调用它们的方式不同：

  1. deck.selectionSort();      // 修改当前Deck对象
  2. deck = deck.mergeSort();   // 将当前Deck对象替换为新的Deck对象

练习13-4

这个练习旨在通过实现插入排序来践行自上而下的编程。请访问 http://www.sorting-algorithms.com/insertion-sort，阅读其中对插入排序的介绍，再编写一个名为 insertionSort 的方法来实现这种算法。

练习13-5

为 Deck 类编写方法 toString。它应该返回一个对 Deck 对象中的扑克牌作了描述的字符串。该字符串的内容应与 13.1 节中的方法 print 的输出相同。

提示：可用运算符 + 来拼接字符串，但效率不太高。为提高效率，可考虑使用 java.util.StringBuilder；要查找有关这个类的文档，可在网上搜索 Java StringBuilder。