课后习题
问：对下面的三个序列对，对每一对序列，判断第二个序列是否会出现在第一个序列的排序过程中。
答：考察插入排序、归并排序、快速排序、堆排序。我觉得这道题的难点在于要在20分钟之内解决。（试卷11道题只给了110分钟，本题占据最高的3分）
问：为什么Java的Arrays.sort对int、long、char这样的基本数据类型数组采用快排，但对对象类型数组却采用归并排序呢？
答：经过一番查阅，这个问题的答案应该是稳定性。快排是不稳定的（61B的讲义提到稳不稳定取决于分区策略，我有点迷茫了），而归并排序是稳定的。我们希望排序对象类型数组时它是稳定的，所以才采用归并排序。比如讲义中提到的将学生根据名称排序，如果名称相同则再根据学分排序。在这里如果排序算法不稳定，那么学分排序之后名称相同的学生的相对顺序就会被破坏。