排序算法
排序算法.png
- 排序算法的稳定性：就是相同值的两个元素会不会改变它们的次序，不改变就是稳定，改变了就是不稳定。
选择排序
基本思想：从首个开始，过滤整个数据找到第一小和首位进行交换。下一轮从第二个开始找到第二小和第二位交换……
冒泡排序
基本思想：相邻两数比较，交换，大的放后面。
和选择排序的不同在于：相邻的进行比较、交换……
插入排序
简单排序中最好用的一种。
基本思想：（可以类比于打扑克牌时在自己手里整理牌）前方的是已排好序的部分（起初数量为 1 个），后面的逐个插入到前方已排好序的部分（插入的位置之后的有序的位置顺序后移）。
希尔排序
改进的插入排序。
基本思想：以固定间隔对应的值先排序（插排）；缩小间隔直到间隔为 1。
优点主要在：间隔大时移动的个数少；间隔小时移动的距离短。
归并排序
基本思想：（分块递归）f(n) 为数组分两半，分别对两半进行排序（同样用 f(n)），最后将两半整合（二路归并）。
时间复杂度： N 个数大概分 logN 次，每个小组排序时间大概为 N，所以是 O(NlogN)
空间复杂度：因为使用了就释放了，所以仅 O(N)
一般语言的对象排序都是归并排序（如 java、python）。对象排序一般要求稳定。
快速排序
快排中经典的叫“单轴快排”，改进的叫“双轴快排”。轴（pivot）。
基本思想：以轴为中心，将比轴小的排前面，大的分后面；（递归）将轴外两部分再次按轴进行分……直到轴两边的元素少于 1 个。
实现方式有优有劣，关键在于找中轴的两侧块的方法（哪个是轴可以任意选）：
- 从一侧出发，小于轴的掠过，大于轴的放后面，最后将轴放在合适的位置（和最后一个小于等于轴的进行交换）。
- 从两侧出发（略过轴），前侧找小于轴的，后侧找大于轴的，两者都找到不符合的，交换一下，继续找，最后将轴放在合适的位置。
时间复杂度：每分一次需要遍历 N 次，分的次数为 logN 次（每次分两半嘛），所以时间复杂度为 N*logN。
空间复杂度：因为每分的一部分都需要临时变量，所以为 logN
- 双轴快排：两个轴，分三部分。
工业上的数组排序（Array.sort() 内部实现，提前预判）
- 一小块一小块排得比较好，归并
- 数组短，插入
- 然后考虑快排
- 取 5 个数，相等，单轴
- 不相等，双轴
计数排序
非比较排序；桶思想的一种。桶排序都是非比较的排序。
适用范围：数组元素的个数比较大，但值都比较小。如员工年龄。
基本思想：数组的下标做为要排序的值，数组元素值作为个数。
空间复杂度： N+K，N 是排序结果数组，K 为桶的个数。
时间复杂度：N+K，N 为元素加加的次数，就是元素的个数；K 为返回结果时对桶的遍历。
计数排序变成稳定的：需要再遍历原数组，按序生成目标数组。
基数排序
非比较排序；桶排序的一种。基数排序本质是一种多关键字的排序。
基本思想：
- 先按个位数进行排序，一样的放一个桶中，再按顺序取出（桶按由小到大排序）；
- 再按十位数进行排序，一样的放一个桶中，再按顺序取出；
- 再按高一位的继续重复上一步，不足的位数按此位为 0 计，直到取到最高位……
- 由于放入和取出是有顺序的，所以在最后取出后结果是由小到大排好序的。
空间复杂度： 可以做到 O(N)。（靠编程技巧）
时间复杂度： 就是一次一次复制。O(N*K)，N 为数据量的个数，K 为建一系列桶的次数，也就是数据的位数。
总结：
- 本质是一种多关键字的排序
- 有低位优先和高位优先两种
- LSD（Least Significant Digit first）低位优先，如上。
- MSD（Least Significant Digit first） 高位优先。递归的思想（我自己的容器的思想）。
桶排序
基本思想：通过分桶，进行排序，桶内再单独排序。最后按顺序输出。
普通的桶算法排序不常用，只有特殊场景才有用。原因：
- 桶内还需要排序
- 不好分桶
- 桶不好用数据存
- 若用 ArrayList（go 里是 slice）会有数据空间增长的问题。
- 若用链表，链表的排序特别麻烦，相当于冒泡思想。
它的时间复杂度和空间复杂度也相当麻烦。
