小结

不论列表是否有序，顺序搜索算法的时间复杂度都是 \$O(n)\$。
对于有序列表来说，二分搜索算法在最坏情况下的时间复杂度是 \$O(logn)\$。
基于散列表的搜索算法可以达到常数阶。
冒泡排序、选择排序和插入排序都是 \$O(n^2)\$ 算法。
希尔排序通过给子列表排序，改进了插入排序。它的时间复杂度介于 \$O(n)\$ 和 \$O(n^2)\$ 之间。
归并排序的时间复杂度是 \$O(nlogn)\$，但是归并过程需要用到额外的存储空间。
快速排序的时间复杂度是 \$O(nlogn)\$，但当分割点不靠近列表中部时会降到 \$O(n^2)\$。它不需要使用额外的存储空间。

讨论题

利用本章给出的公式，计算散列表处于以下情况时的平均比较次数：
- 占用率为10%；
- 占用率为25%；
- 占用率为50%；
- 占用率为75%；
- 占用率为90%；
- 占用率为99%。
  
  你认为在哪种情况下散列表过小？请给出理由。
修改为字符串构建的散列函数，用字符位置作为权重因子。
请为字符串散列函数设计另一种权重机制。这些函数存在什么偏差？
研究完美散列函数。针对一个名字列表（同学、家人等），使用完美散列函数生成散列值。
随机生成一个整数列表。展示如何用下列算法为该列表排序：
- 冒泡排序；
- 选择排序；
- 插入排序；
- 希尔排序（自己决定增量）；
- 归并排序；
- 快速排序（自己决定基准值）。
针对整数列表 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，展示如何用下列算法为该列表排序：
- 冒泡排序；
- 选择排序；
- 插入排序；
- 希尔排序（自己决定增量）；
- 归并排序；
- 快速排序（自己决定基准值）。
针对整数列表 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]，展示如何用下列算法为该列表排序：
- 冒泡排序；
- 选择排序；
- 插入排序；
- 希尔排序（自己决定增量）；
- 归并排序；
- 快速排序（自己决定基准值）。
针对字符列表 ['P', 'Y', 'T', 'H', 'O', 'N']，展示如何用下列算法为该列表排序：
- 冒泡排序；
- 选择排序；
- 插入排序；
- 希尔排序（自己决定增量）；
- 归并排序；
- 快速排序（自己决定基准值）。
为快速排序算法设计另一种选择基准值的策略，比如选择中间元素。重新实现算法，并为随机数据集排序。在什么情况下，你的策略会优于（或劣于）本章所采用的策略？

编程练习

进行随机实验，测试顺序搜索算法与二分搜索算法在处理整数列表时的差异。
随机生成一个有序的整数列表。通过基准测试分析文中给出的二分搜索函数（递归版本与循环版本）。请解释你得到的结果。
不用切片运算符，实现递归版本的二分搜索算法。别忘了传入头元素和尾元素的下标。随机生成一个有序的整数列表，并进行基准测试。
为散列表实现 len 方法（__len__）。
为散列表实现 in 方法（__contains__）。
采用链接法处理冲突时，如何从散列表中删除元素？如果是采用开放定址法，又如何做呢？有什么必须处理的特殊情况？请为 HashTable 类实现 del 方法。
在本章中，散列表的大小为 11。如果表满了，就需要增大。请重新实现 put 方法，使得散列表可以在载荷因子达到一个预设值时自动调整大小（可以根据载荷对性能的影响，自己决定预设值）。
实现平方探测这一再散列技巧。
使用随机数生成器创建一个含 500 个整数的列表。通过基准测试分析本章中的排序算法。它们在执行速度上有什么差别？
利用同时赋值特性实现冒泡排序。
可以将冒泡排序算法修改为向两个方向 “冒泡”。第一轮沿着列表 “向上” 遍历，第二轮沿着列表 “向下” 遍历。继续这一模式，直到无须遍历为止。实现这种排序算法，并描述它的适用情形。
利用同时赋值特性实现选择排序。
针对同一个列表使用不同的增量集，为希尔排序进行基准测试。
不使用切片运算符，实现 mergeSort 函数。
有一种改进快速排序的办法，那就是在列表长度小于某个值时采用插入排序（这个值被称为 “分区限制”）。这是什么道理？重新实现快速排序算法，并给一个随机整数列表排序。采用不同的分区限制进行性能分析。
修改 quickSort 函数，在选取基准值时采用三数取中法。通过实验对比两种技巧的性能差异。