数据结构——排序算法总结

一、插入排序

插入排序是算法是每次将1个待排序的记录按其关键字大小，插入到前面己排好序的子序列中，直到全部记录插入完成。

直接插入排序 （实现简单） 空间复杂度：仅使用了常数个辅助单元，$O(1)$ 时间复杂度：最好情况下为$O(n)$，最坏情况为$O(n^2)$ 稳定性：稳定折半插入排序 即先折半查找出元素的待插入位置，然后统一移动待插入位置之后的所有元素 。折半插入排序减少了比较元素的次数，这部分的复杂度为$O(nlo{g}_{2}n)$，而元素的移动次数并未改变。因此，折半插入排序的时间复杂度仍为$O(n^2)$。依旧是稳定排序。希尔排序（了解） 空间复杂度：$O(1)$ 时间复杂度：最好情况下为$O(n^{1.3})$，最坏情况为$O(n^2)$ 稳定性：不稳定

二、交换排序

交换排序是指，根据序列中两个元素关键字的比较结果来交换这两个记录在序列中的位置。其中冒泡排序和快速排序属于交换排序这种算法。

冒泡排序 一趟冒泡排序是指，从后往前（或从前往后）两两比较相邻元素的值，若$A[i-1]>A[i]$，则交换这两个元素，直到该整个列比较完毕。如此，算作一趟，效果是将最小的元素交换到待排序列的第一个位置上（或将最大的元素交换到待排序列的最后1个位置）。 空间复杂度：$O(1)$ 时间复杂度：最好情况下为$O(n)$，最坏情况为$O(n^2)$，平均时间复杂度为$O(n^2)$ 稳定性：由于$i>j且A[i]=A[j]$时，不会交换，因此冒泡排序是稳定的快速排序 快速排序方法是一种分治思想。 空间复杂度：由于快速排序是递归的，需要借助一个递归工作找来保存每层递归调用的必要信息，其容量应与递边归调用的最大深度一致。最好情况下为$O(lo{g}_{2}n)$，最坏情况为$O(n)$，平均情况下栈的深度为$O(lo{g}_{2}n)$ 时间复杂度：快速排序的运行时间与划分是否对称有关。若每一次的划分都尽可能平衡，此时时间复杂度为$O(nlo{g}_{2}n)$，最坏情况为$O(n^2)$ 稳定性：不稳定

三、选择排序

算法步骤为首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

简单选择排序 空间复杂度：仅使用了常数个辅助单元，$O(1)$ 时间复杂度：$O(n^2)$ 稳定性：不稳定$堆排序$ 算法及动画演示：https://www.runoob.com/w3cnote/heap-sort.html 空间复杂度：仅使用了常数个辅助单元，$O(1)$ 时间复杂度：建立堆为$O(n)$，每次调整为$O(h)$，因此总的时间复杂度为$O(nlo{g}_{2}n)$ 稳定性：不稳定

四、归并排序

原理及动画演示：https://www.runoob.com/w3cnote/heap-sort.html 对于2路归并算法 空间复杂度：Merge()操作中，辅助存储空间为n个单元，所以空间复杂度为$O(n)$ 时间复杂度：每趟归并所需为$O(n)$，共需$\lceil lo{g}_{2}n\rceil$趟，因此时间复杂度为$O(nlo{g}_{2}n)$

五、基数排序（待学习）

原理及动画演示：https://www.runoob.com/w3cnote/radix-sort.html

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序是一种稳定的排序算法。

---

参考： [1] 维基百科 [2] 菜鸟教程 [3] 王道数据结构考研复习指导