一般练习

1. 复习下面概念：排序问题，全序关系，反对称关系，等价类，排序方法（排序算法），堆排序算法，基于关键码比较的排序，排序码，内排序，外排序，外排序算法，归并排序算法，排序中的基本操作（关键码比较和数据记录移动），最优排序算法，原地排序算法，稳定性，适应性，插入排序，选择排序，交换排序，分配排序，直接插入排序算法，二分法插入排序算法，shell排序算法，直接选择排序算法，树形选择，交换和排序，逆序，起泡排序算法，交错起泡排序，快速排序，划分，归并排序算法，归并操作，二路归并，分配排序，多轮分配和收集，高位优先方法，低位优先方法，基数排序，混成排序方法，蒂姆排序算法，主关键码，其他关键码。

2. 设有个元素的序列（表），元素可以比较大小，但排列没有任何顺序保证。现希望选出其中最大的100个元素，或希望找到其中从大到小排在第100位的元素，怎样能最快找到这个元素？操作的复杂性如何？

3. 现在有个整数关键码，需要把其中的负值调整到非负值之前。请设计一个算法完成这一工作，要求：只使用O(1) 空间，时间复杂度是O(n)。请分析你的算法在执行中总共需要做多少次关键码比较。

4. 假设现在要处理的数据项的关键码是整数，请考虑一种算法，它能最快地将关键码小于-10的项移到左边，关键码大于10的项移到右边，中间是关键码介于-10和10之间的数据项。你的算法应该在线性时间完成工作，而且要尽量快速。

5. 假设有个不同的关键码，希望找到其中最大的关键码和最小的关键码。最直截了当的方法需要做次关键码比较。请设计一种方法，不需要做次比较就能找出所需的值。你的算法需要做多少次比较？

6. 数据序列（数据集）的中位值是统计中的重要概念。请设计一个算法，它能在线性时间内找到一组整数的中位值。

编程练习

1. 请用一组随机生成的数据试验本章正文中讨论的几个排序算法，关键码用某个范围内的整数表示。分析得到的试验数据，并对其做一些总结。

2. 请定义一个插入排序算法，让它在原序列的高端积累已排序的元素。

3. 请采用二分法在插入排序中找到插入位置，而后再实际插入元素。请分析所做的算法，特别关注其稳定性。如果它不稳定，请设法修改使之稳定。

4. 请定义一个选择排序函数，它每次选择剩余记录中最大的记录，完成从小到大递增顺序的排序工作。

5. 请实现一个稳定的选择排序算法。

6. 第9.2.3节最后提出了一种交错起泡的排序技术。请定义一个采用这种技术的排序函数，并用随机生成的表做一些试验，比较它和简单起泡排序的性能。

7. 请为第3章的单链表类定义一个采用选择排序思想的排序方法。

8. 请为第3章的单链表类定义一个采用快速排序思想的排序方法。

9. 请实现采用“三者取中”策略的快速排序函数，用随机生成的表作为实例，比较采用这种策略的函数和本章正文中的快速排序函数。

10. 请提出另一种改进划分标准的方法，基于该方法实现一个快速排序函数，并将实现的函数与正文中的快速排序函数比较。

11. 请实现一个非递归的快速排序算法，算法在选择处理分段时采用本章正文中提出的相关方法，保证其空间需求达到最少。

12. 考虑9.5.1节提出的基于绩点对学生记录排序的工作。请根据具体情况做出一种设计和实现，保证排序工作可以在O(n) 时间完成（n是学生记录数）。

13. 第9.5.1节最后说基数排序算法的另一种常见技术是用链接表实现桶，那样做可以摆脱Python中list操作的潜在影响（空间复杂度不再依赖于Python表操作的实现技术）。用链表作为记录存储桶，收集时可以简单地取下链表结点链，顺序连接起来，因此可以节省时间。请采用这种技术实现一个基数排序函数。

14. 请考虑9.5.2节提出的组合方法，选择一种组合方式实现相应的排序函数，并通过一些试验确定合适的方法转换时机。

15. 请基于蒂姆排序算法实现一个排序函数。