一、冒泡排序
1、什么是排序，应用广泛吗？
-
排序：就是对一组具备可比性的数组进行重新排列顺序（升序 or 降序） - 排序的应用无处不在
2、初步认识十大排序算法（目前有个印象就行）？
image.png
3、体验一遍冒泡排序的动画过程，深入记忆冒泡排序的过程（深入骨髓的那种深入）？
冒泡排序.gif
4、冒泡排序第一版（最简版本，要能口述思路）？
public static void bubbleSort_1(Integer[] array) {
for (int end = array.length -1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) { //交互位置
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
}
}
}
}
5、 冒泡排序优化①（要能口述优化思路）
- 如果我们的数组本就是比较有顺序，那么我们可以提前退出循环
- 但是针对无序数列，将会不起什么作用
public static void bubbleSort_2(Integer[] array) {
for (int end = array.length -1; end > 0; end--) {
boolean isResorted = false;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) { //交互位置
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
isResorted = true;
}
}
if (!isResorted) break;
}
}
对 10w 个有序数列处理速度对比
对 3w 个无序数列处理速度对比
6、 冒泡排序优化②（要能口述优化思路）
- 上面的优化受众面太过小，要求数列经过前几次交换后完全有序比较有效
- 换个思路优化：
如果序列尾部已经局部有序，可以记录最后 1 次交互的位置，减少比较次数
image.png
public static void bubbleSort_3(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
int lastSwapIndex = 1;
for (int begin = 1; begin <= end; begin++) {
if (array[begin - 1] > array[begin]) { //交互位置
int temp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = temp;
lastSwapIndex = begin;
}
}
end = lastSwapIndex;
}
}
对 3w 个一半有序的数据排序
对 3w 个完全无序的数据排序
7、 冒泡排序的最优时间复杂度、最差时间复杂度、平均时间复杂度分别是多少？
- 最优时间复杂度：O(n)
- 最差时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
二、选择排序
1、简述选择排序的主要思想（重要）？
image.png
2、选择排序的最好、最坏、平均时间复杂度是多少？空间复杂度是多少？属于稳定排序吗？
- 最好、最坏、平均时间复杂度是 O(n^2)
- 空间复杂度: O(1)
- 属于
不稳定排序，上面的汇总图有误
3、 选择排序和冒泡排序的性能对比如何？
- 虽然冒泡排序优化算法后最好时间复杂度可以达到O(n)，但是
数组要求有序属于特例情况 - 选择排序的交互次数要远远少于冒泡排序，平均性能优于冒泡排序
image.png
4、 选择排序是否还有优化空间？
- 可以，可以使用堆来选择最大值
- 也就是我们接下来学习的
堆排序
三、堆排序
1、口述堆排序的过程（重要）？
image.png
2、堆排序的最好、最坏、平均时间复杂度是多少？空间复杂度是多少？属于稳定排序吗？
- 最好、最坏、平均时间复杂度是 O(nlogn)
- 空间复杂度: O(1)
- 属于
不稳定排序
3、对冒泡、选择、堆排序的性能对比图
3w 个随机数据进行排序的性能对比
3w 个一半有序的数据进行排序
