数据结构-排序（一）绪论
source link: https://mr00wang.github.io/2021/11/23/Sort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数据结构-排序（一）绪论
排序（Sort） ，就是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。
输入： n个记录R1,R2,…,RnR1,R2,…,Rn，对应的关键字为k1,k2,…,kn。k1,k2,…,kn。
输出：输⼊序列的⼀个重排R1′,R2′,…,Rn′，R1ʹ,R2ʹ,…,Rnʹ，使得有k1′≤k2′≤…≤kn′k1ʹ≤k2ʹ≤…≤knʹ（也可递减）
排序算法的评价指标：①时间复杂度；②空间复杂度
算法的稳定性： 若待排序表中有两个元素RiRi 和RjRj，其对应的关键字相同即keyi=keyjkeyi=keyj，且在排序前的前⾯RiRi 和RjRj，若使⽤某⼀排序算法排序后， RiRi 仍然在 RjRj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
分类：
- 内部排序：数据都在内存里（关注如何使算法时、空复杂度更低 ）
- 外部排序：数据太多，无法全部存在内存里（还要关注如何使读/写磁盘次数更少）
算法 时间复杂度
空间复杂度 稳定性
最好 最差 平均
直接插入排序 O(n)O(n) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 稳定
折半插入排序 O(n)O(n) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 稳定
希尔排序 不确定 O(n2)O(n2) O(n1.25）～O（1.6n1.25）O(n1.25）～O（1.6n1.25） O(1)O(1) 不稳定
冒泡排序 O(n)O(n) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 稳定
快速排序 O(nlog2n)O(nlog2n) O(n2)O(n2) O(nlog2n)O(nlog2n) O(log2n)O(log2n) 不稳定
简单选择排序 O(n2)O(n2) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 不稳定
堆排序 O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(1)O(1) 不稳定
归并排序 O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(n)O(n) 稳定
基数排序 O(d(n+rd))O(d(n+rd)) O(d(n+rd))O(d(n+rd)) O(d(n+rd))O(d(n+rd)) O(n+rd)O(n+rd) 稳定
时间空间复杂度网站推荐：https://www.bigocheatsheet.com/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK