chapter12
复制本地路径 | 在线编辑
1. 快速排序
1.1 给出一个实例，说明快速排序无法保证稳定性(三种实现方式均给出)
1.2 说明快速排序的平均性能为O(1.3logn)
1.3 分别给出三种快速排序的关键代码
2. 若众数的定义为某个数多于任意其他元素
2.1 给出众数选取的代码(先找候选，随后判断)
2.2 判断: 众数候选选出的数一定是原数组中出现最多的数
2.2 众数候选选出的数出现的频率最低是多少
3. 若众数的定义为某个数不少于其他元素
3.1 给出众数选取的代码(候选算法需要进行调整)
4. 等长有序数组合并，给出求合并后的中位数算法
5. 不等长的两个有序数组合并，给出合并后的中位数算法
5.1 首先要把过长的数组剪短，那么多少才能算作过长呢
5.2 短数组找一个点，长数组找两个点，这几个点的位置在哪
5.3 根据这三个点大小判断后，如何进行剪切
6. 利用中位数算法，给出两有序数组合并后第k个元素的算法
7. 寻找第k个数
7.1 利用快速排序，求该算法的平均时间复杂度
7.2 利用最大堆最小堆，说明三种实现方式
7.2 利用k选取算法，给出该算法的具体流程
7.3 说明k选取算法的时间复杂度为O(n)
8. 希尔排序
8.1 希尔序列 : 复杂度为O(n^2)
8.2 Papernov序列 : 复杂度为O(n^3/2)
8.3 Pratt序列 : 复杂度为O(n(logn)^2)
8.4 给出希尔排序的一个实例