数据结构与算法之美 - 学习笔记 为什么插入排序比冒泡排序更受欢迎
Q：插入排序和冒泡排序的时间复杂度相同，都是 O(n²),在实际的软件开发中,为什么更倾向于使用插入排序算法而不是冒泡排序算法
评价、分析一个"排序算法"
排序算法的执行效率
最好情况、最坏情况、平均情况时间复杂度。有序度不同的数据，对于排序执行时间有一定影响
时间复杂度的系数、常数、低阶
时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势。在实际开发中，往往数据规模没那么大，需要把同阶时间复杂度的算法的系数、常数、低阶考虑进来
- 比较次数和交换（移动）次数
基于比较的排序算法的执行过程，涉及两种操作：比较元素大小，元素移动。在分析执行效率时，需要把比较次数和移动次数考虑进去
排序算法的内存消耗
原地排序算法，特指空间复杂度是 O(1)的排序算法
排序算法的稳定性
稳定性，是指在待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。适用于多次排序，下一次排序依赖上一次排序的稳定结果
冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，不满足就进行交换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
优化点：冒泡排序可能会提前结束。即当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作
结合代码
// 从小到大排序数组
function bubbleSort(arr) {
if (arr.length <= 1) return;
for (var i = 0; i < arr.length; i++) {
// 提前结束标识 本轮是否有数据交换
var exchange = false;
// i标识已排序完成的数，-1表示最后一个元素无需遍历，因为j+1比较过这个数
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
exchange = true;
}
}
if (!exchange) return arr;
}
return arr;
}
结合分析排序算法的三个方面有
- 冒泡排序是原地排序算法：冒泡过程只涉及相邻数据的交换操作，需要常量级的临时控件，其空间复杂度为 O(1)
- 冒泡排序是稳定的排序算法：在冒泡排序中，只有交换才会改变两个元素顺序，两个元素相等时不进行交换，因此相同大小的数据在排序前后不会改变顺序
- 冒泡排序的时间复杂度
[图片上传失败...(image-484d4b-1634033189522)]
平均时间复杂度：不同的排列方式，时间复杂度不同，这里通过“有序度”和“逆序度”进行分析
- 有序度是数组中具有有序关系的元素对的格式 n*(n-1)/2
- 满有序度是完全有序的数组的有序度
- 逆序度=满有序度-有序度
对于包含 n 个数据数组进行冒泡排序，平均交换次数分析如下：
最坏情况，初始状态有序度为 0，要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度为 n(n-1)/2，无需进行交换。
取中间值 n*(n-1)/4，表示初始有序度的平均情况
因此在平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定比交换操作多，而最坏复杂度为 O(n²)，所以平均情况下的
时间复杂度就是 O(n²)
插入排序
将排序数组数据分为两个区间，已排序区间和未排序区间。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的位置插入，并保证已排序区间数据一直有序
结合代码
// 从小到大排序数组
function insertionSort(arr) {
if (arr.length <= 1) return;
// 待插入元素
for (var i = 1; i < arr.length; i++) {
// 与有序元素区间元素比较
var j = i - 1;
var item = arr[i];
for (; j >= 0; j--) {
// 数据移动
if (item < arr[j]) {
arr[j + 1] = arr[j];
} else {
break;
}
}
// 插入数据
arr[j + 1] = item;
}
return arr;
}
分析插入算法
- 插入排序是原地排序算法：比较寻找合适插入位置的过程，并不需要额外控件，其空间复杂度为 O(1)
- 插入排序是稳定的排序算法：对于值相同的元素，可以选择将后面出现的元素插入到前面出现的元素后面，因此相同大小的数据在排序前后不会改变顺序
- 插入排序的时间复杂度：
如果要排序的数据是有序的，每次只需要比较一个数据就能确定插入位置，这种情况下，最好的时间复杂度是 O(n)。这里是从尾到头遍历已经有序的数据
相反数据是倒序的情况下，最坏时间复杂度为 O(n²)
执行一次数据插入操作的时间复杂度为 O(n)，对插入排序来说需要执行 n 次插入操作，其平均时间复杂度为 O(n²)
选择排序
选择排序类似插入排序，同样分为已排序区间和未排序区间。不同的是，选择排序每次都从未排序区间中取出最小/大的数据，放置到排序区间的末尾。直至未排序区间无数据
结合代码
function selectionSort(arr) {
if (arr.length <= 1) return;
// 已排序区间
for (var i = 0; i < arr.length; i++) {
var j = arr.length - 1;
var item = arr[j];
var minIndex = j;
// 未排序区间中寻找最小值
for (; j > i; j--) {
if (item > arr[j - 1]) {
item = arr[j - 1];
minIndex = j - 1;
}
}
// 放置到排序区间末尾
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
分析选择排序
- 是原地排序算法，其空间复杂度为 O(1)
- 最好、最坏、平均时间复杂度都为 O(n²)。无论数据排序情况如何，每次选择操作，都需要从未排序区间中寻找最小/大数据（遍历）
- 选择排序不是稳定性的排序算法，每次从未排序区间中寻找最小/大数据，并和前面的元素交换位置，破坏了稳定性
解答开篇
Q：为什么插入排序比冒泡排序更受欢迎？
冒泡排序和插入排序的时间复杂度都为 O(n²)，但实际操作上，插入排序的性能较高些。因为冒泡排序的数据交换比插入排序的数据移动要复杂，冒泡排序一次数据交换需要用到 3 个赋值操作，而插入排序的数据移动只需要 1 个
总结
评价、分析一个排序算法需要从算法执行效率、内存消耗、稳定性三方面考虑。
