一、快速排序（Quick Sort）
1、快速排序是 1960 年发明的，到现在还没有明显优于他的算法出现，这说明什么？
- 说明学习算法的有效性是很久很久的，五六十年都没过期，
真是一次学习，终生受益
image.png
2、快速排序的核心思想是什么（一句话概括）？
确定一个
轴点元素(pivot)，小于 pivot 的放左边，大于 pivot 的放右边，等于 pivot 的元素放哪边都可以本质：逐渐将每一个元素都转换成轴点元素
image.png
3、快速排序轴点的构造过程如下（一定要能理解，重要，有空画一画）？
image.png
4、快速排序的代码实现？(能回忆起大框架逻辑即可)
public class QuickSort<T extends Comparable<T>> extends Sort<T> {
@Override
protected void sort() {
sort(0, array.length);
}
private void sort(int begin, int end) {
if (end - begin < 2) return;
int pivotIndex = pivotIndex(begin, end);
sort(begin, pivotIndex);
sort(pivotIndex + 1, end);
}
private int pivotIndex(int begin, int end) {
T pivotValue = array[begin];
end--; //让 end 指向末尾元素
while (begin < end) {
while (begin < end) {
if (cmp(pivotValue, array[end]) < 0 ) { //如果尾部元素大于轴点元素
end--;
} else { //如果尾部元素小于等于轴点元素，先交换，再掉头
array[begin] = array[end];
begin++;
break;
}
}
while (begin < end) {
if (cmp(array[begin], pivotValue) < 0) { //如果头部元素小于轴点元素
begin++;
} else { //如果头部元素大于等于轴点元素，先交换再掉头
array[end] = array[begin];
end--;
break;
}
}
}
array[begin] = pivotValue;
return begin;
}
}
5、快速排序的时间复杂度如何计算？
image.png
image.png
6、如何避免快速排序的最坏时间复杂度的出现（从 pivot 选择方面考虑）？
- 上述我们编写的快速排序代码存在一个问题，当对 3w 个有序数组排序时，会发现栈溢出了，为什么？
栈溢出
因为我们上述代码，对有序数列进行排序，会退化成 O(n^2) 的最坏时间复杂度，导致开辟过多栈空间，所以栈溢出了。
为了减低最坏情况的出现概率，一般采取的做法是：
随机选择轴点元素
//在pivotIndex加上一行随机选择 pivot 的代码即可解决
private int pivotIndex(int begin, int end) {
//随机选择 pivot
swap(begin, begin + (int)(Math.random() * (end - begin)));
T pivotValue = array[begin];
end--; //让 end 指向末尾元素
...
image.png
7、为什么我们在快速排序确定 pivot 的时候，如果遇到和 pivot 相等的元素，选择将它甩到对立面？
- 目的就是减少最坏复杂度情况出现
如果不将相等元素甩到对立面，对 1 万个 1 进行排序，发现快速排序的效率退化及其严重
如果将相等元素甩到对立面，对 1 万个 1 进行排序，快速排序的效率依然很高
image.png
二、希尔排序（Shell Sort）
1、希尔排序是什么（基本概念）？
image.png
2、希尔排序的实例（辅助理解希尔排序的核心思想）？希尔排序是对什么排序的优化？
-
可以认为希尔排序是对插入排序的优化
image.png
image.png
3、希尔排序的关键因素 - 步长序列？
image.png
image.png
private List<Integer> shellStepSequence() {
List<Integer> stepSequence = new ArrayList<>();
int step = array.length;
while ((step >>= 1) > 0) {
stepSequence.add(step);
}
return stepSequence;
}
private List<Integer> sedgewickStepSequence() {
List<Integer> stepSequence = new LinkedList<>();
int k = 0, step = 0;
while (true) {
if (k % 2 == 0) {
int pow = (int) Math.pow(2, k >> 1);
step = 1 + 9 * (pow * pow - pow);
} else {
int pow1 = (int) Math.pow(2, (k - 1) >> 1);
int pow2 = (int) Math.pow(2, (k + 1) >> 1);
step = 1 + 8 * pow1 * pow2 - 6 * pow2;
}
if (step >= array.length) break;
stepSequence.add(0, step);
k++;
}
return stepSequence;
}
4、希尔排序的代码实现？
image.png
- 可以看到，希尔排序就是内部嵌套了个插入排序 （希尔其实在减少
逆序对）
对 3w 个无序数据排序，可以看到希尔排序对比插入排序大大得到提升
