“纵浪大化中，不喜亦不惧。”
前言
考前总结一下
一些排序算法，期末考必考嗷~
排序
代码实现：Sort 方法 GitHub
基于比较的排序算法时间下限是 O（nlogn）：归并排序、堆排序、快排。其他都是 O（n^2）
插入排序
直接插入
循环 n-1 次，每次将无序序列的第一个数插入到有序序列中。一开始有序序列只有一个数（第一个数），之后每插入一个有序序列+1
将第一个数作为哨兵，每次移动都将插入位置后到该数前的所有数往后移动一位
时间复杂度：O(n^2)
- 最好情况：已经是有序序列，只用比较 n-1 次（因为是从后往前比较），不用移动。
- 最坏情况：逆序序列，每次向前比较到哨兵
空间复杂度：O（1）
稳定
折半插入
其实是在直接插入的基础上，将无序序列的第一个数在有序序列中查找的时候变为折半查找
移动次数和直接插入相同，依赖于初始序列
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定
希尔排序
将一组序列分组进行排序（隔 5 个数一组，隔 3 个一组…）
做到基本有序后对全体进行直接插入，因为基本有序，所以比较和插入次数能有效减少
时间复杂度：O（n^1.25）~O（1.6n^1.25）
空间复杂度：O（1）
不稳定
交换排序
冒泡排序
进行 n-1 次，从第一个数开始，两两比较，把大的数放后面。从而每次排序能确定最大的数并放到最后
当某次冒泡过程中不存在数值交换，则已为正序，不用再进行排序
时间复杂度：O（n^2）
- 最好情况：正序，进行一次排序，比较 n-1 次，不移动
- 最坏情况：逆序，n-1 次排序，每次都要移动
空间复杂度：O（1）
稳定（可以通过改变比较条件更改）
快速排序
从冒泡的基础上改进，其核心是划分
从头到尾，从尾到头分别开始扫描，一般以第一个数为划分。
把第一个数存起来，从后往前扫，如果有个数小于存起来的，就存到前面还没开始扫描的数（这个数被存起来，所以不怕被覆盖）；然后从前往后开始扫描，如果有个数大于存起来的，就给到现在后面扫描停住的那个数，然后把存起来的数再给。继续扫描直到两个扫描碰头
最好情况：每次划分后划分的元素在中间，将序列分为两个长度大致相等的子序列
最坏情况：每次划分后划分的元素在头或者在尾
减少最坏情况发生的概率：
- 预处理：洗牌
- 随机选一个数作为划分参照
- 选取中位数（这种方法看起来很好，但是因为正序和逆序的中位数是一样的，所以不用这种方法）
- 第一个数、最后一个数、中位数，三者取中（最好用）
时间复杂度：O（n^1.25）~O（1.6n^1.25）
- 最好情况：O（nlogn）
- 最坏情况：O（n^2）
空间复杂度：递归调用产生空间
- 最好情况：O（logn）
- 最坏情况：O（n）
不稳定
选择排序
简单选择排序（直接选择排序）
先扫描一遍（不移动），找到最小的数后与第一个再进行交换。前面的有序序列从没有开始到越来越长，最后整体有序
时间复杂度：O（n^2）
- 最好情况：正序，只比较不移动
- 最坏情况：逆序，移动 3（n-1）次
空间复杂度：O（1）
不稳定
堆排序
堆排序是对树形选择排序的改进，利用线性表以完全二叉树的逻辑结构表示。设父节点的下标值为 n，n/2 及 n/2+1 为其子结点
因为完全二叉树用顺序表表示，因此不能用于链式结构
建堆的比较次数较多，记录少时不宜采用
堆排序利用了大根堆和小根堆的特征：
- 大根堆：根节点（堆顶）的关键字比所有子节点的关键字都大。其左子堆和右子堆分别都是最大堆
- 小根堆：根节点（堆顶）的关键字比所有子节点的关键字都小。其左子堆和右子堆分别都是最小堆
堆排序需要经过一下几个步骤：
- 建堆：将输入序列变为完全二叉树，之后将其调整为大根堆（调整堆）
- 排序
- 输出堆顶，调整堆
时间复杂度：O（nlogn）
- 最好情况：正序，只比较不移动
- 最坏情况：逆序，移动 3（n-1）次
空间复杂度：O（1）
不稳定
归并排序
将两个或两个以上的有序表合并成一个大的有序表
一开始的无序序列中，我们将每个元素独自看成是一个有序表。
二路归并：将初始元素两两归并，每个小有序表中有两个元素。再次两两归并，有四个元素…重复归并直到全完有序
时间复杂度：每次归并比较次数不超过 n，元素移动 n 次。O（nlogn）
空间复杂度：由于递归，辅助空间和待排序元素相等。O（n）
稳定
基数排序
基数排序已经不是基于比较的排序
比如多关键字排序，运用到多个关键字，因此时间复杂度不仅仅取决于数据规模
比如桶排序，比如升序输出工人工龄的时候，方法一是建立工人序列，根据工人排序输出；方法二是建立工龄序列，每次输入工人的时候在相应工龄+1，最后遍历该序列输出。方法二就是桶排序，显然简单很多
