15. 排序算法

排序的分类

一般我们将排序能不能根据输入数组后能否优化处理的特性将排序算法分为两类

Non-Adaptive Sort: 不会根据输入数据的特性进行优化处理
Adaptive Sort: 会根据输入数据的特性进行优化处理

冒泡排序 bubble sort

用两个指针，逐个将相邻的两个节点大小进行比较，每次把最极端的值放到数组的某一边，然后下一层循环减小空间

时间复杂度 $O(n^2)$
空间复杂度 $O(1)$

Adaptive 策略

如果在一次遍历中没有发生任何元素的交换，说明数组已经有序，可以提前结束排序

选择排序 selection Sort

每次遍历一个数组，找到最极端的值然后和边界值进行互换，再在剩下的空间完成剩余的排序

时间复杂度 $O(n^2)$
空间复杂度 $O(1)$

Adaptive 策略

在极端值的时候，如果index和交换目标相同，那么就不交换 (这里其实基本上没有优化)

插入排序 insertion sort

对于一个正在构建的数组(数据流)，每到来一个元素我们都会需要将新变量插入到本来已经有序 (sorted) 的数组中去，一个简单的思路就是，从后往前，逐个和前一个元素进行大小比较，如果比前一个元素小，就把前一个元素后移，直到找到停止位置，将当前的元素放入当前的空位
如果对于一个已经放好的数组，我们的做法应该是从前向后遍历数组，逐个对每一个元素及其前面的部分做插入排序 (插入元素为当前的元素) 这样每次都能保证前面 i 个有序

时间复杂度 $O(n^2)$ $O (n^{2})$
- 对输入数据的情况很敏感
- 最差情况下比较次数为 $\frac{n^2}{2}$ , 移动次数为 $\frac{n^2}{2}$
- 最好情况下比较次数为 $n-1$ , 移动次数为 $0$
- 平均情况下比较次数为 $\frac{n^2}{4}$ , 移动次数为 $\frac{n^2}{4}$
空间复杂度 $O(1)$

Adaptive 策略

存储最小值(最靠前的值) 从而防止每次都需要将最小值移动到最前面
在经典插入排序中，我们一般是将插入值不断执行 swap 操作，但是这个效果并不好，用 arr[i] = arr[i - 1] 的方式会更快
减少交换次数，不小就不交换

优点 advantage

原数组有序
稳定
算法可以微调优化
对于数字 $n$ 较小的时候是最快的算法

快速排序 quick sort

归并排序 merge sort

这个算法要用到分治算法的思路, 即将一个完整的数组从中间分成两部分, 然后对左右两部分分别进行排序, 最后将两部分合并
分治会导致递归树高 $O(\log n)$ , 每一层的复杂度是 $O(n)$ , 因此总的时间复杂度是 $O(n\log n)$
合并的代码用 c++ 的奇技淫巧写起来很优雅

// 输入是 两半数组，即 [left, mid) [mid, right)
for(size_t i = left, j = mid, k = 0; k < n; ++k){
  if(i == mid) temp[k] = arr[j++];  // 左边用完了
  else if(j == right) temp[k] = arr[i++];
  else temp[k] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
}