数据结构——排序（空间复杂度、时间复杂度、性能等分析）
目录
（1）插入排序1
①直接插入排序1
②折半排序1
③希尔排序（缩小增量排序）1
（2）交换排序2
①冒泡排序2
②快速排序2
（3）选择排序2
①简单选择排序2
②堆排序2
（4）二路归并排序3
（5）基数排序3
（1）插入排序
①直接插入排序
【空间】O(1)
【时间】排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟
最好O(n)，元素已有序，每插入一个元素都只需比较一次而不用移动元素
最坏O(n2)，初始为逆序，总比较次数达到最大∑i=2n i，总的移动次数达到最大∑i=2n （i+1）
平均O(n2)，初始顺序随机，总的比较次数和移动次数均约为n2/4
【比较次数与初始状态】√
【移动次数与初始状态】√
【一趟排序一个关键字到达最终位置】×，如1,2,3,4,5,0在最后一趟排序前没有任何一个关键字到达最终位置
【稳定性】√ 每次插入元素总是从后向前比较再移动，不会出现相同元素相对位置变化
【适用性】基本有序，数据量不大；顺序存储、链式存储（大部分排序只适用于顺序存储）
②折半排序
【空间】O(1)
【时间】相比于直接插入排序，查找插入位置上花的时间大大减少
最好O(nlog2n)，
最坏O(n2)，
平均O(n2)，
【比较次数与初始状态】×，仅取决于表中元素个数n（二叉排序树高）
【移动次数与初始状态】√
【一趟排序一个关键字到达最终位置】×
【稳定性】√
【适用性】关键字较多时
③希尔排序（缩小增量排序）
将待排序表按选区的“增量”分割成若干个特殊的子表，进行直接插入排序，希尔排序每趟都会使整个序列变得更加基本有序，最后再来一趟直接插入排序效率更高
增量选取
①希尔：⌊n/2⌋，⌊n/4⌋……⌊n/2k⌋……2,1
②帕佩尔诺夫和斯塔舍维奇：2k+1，……65,33，17,9,5,3,1，其中k为大于1的整数，2k+1<n,增量序列末尾的1是额外添加的，此时时间复杂度为O（n1.5）
注：①增量序列最后一定是1②增量序列中的值应尽量没有除1以外的公因子（素数）
【空间】O(1)
【时间】依赖于增量系列
最坏O(n2)
平均O(nlog2n)
n在特定范围内，O（n1.3）
【比较次数与初始状态】
【移动次数与初始状态】
【一趟排序一个关键字到达最终位置】
【稳定性】×，相同关键字可能被划分到不同的子表可能会改变他们的相对次序
【适用性】仅适用于顺序存储
（2）交换排序
①冒泡排序
在一趟排序过程中没有发生关键字交换则冒泡排序结束
【空间】O(1)
【时间】
最好O(n)，初始有序，比较n-1次，移动0次
最坏O(n2)，初始逆序，需要n-1趟排序，第i趟比较n-i次，每次需要移动元素3次交换元素位置，共比较次数∑i=1n-1 (n-i）=n(n-1)/2，移动次数∑i=1n-1 3(n-i）=3n(n-1)/2
平均O(n2)
【比较次数与初始状态】√
【移动次数与初始状态】√
【一趟排序一个关键字到达最终位置】√
【稳定性】√
【适用性】
②快速排序
划分思想，一趟后划分为左右两部分
【空间】递归需要栈，最好⌈log2(n+1) ⌉次即O(log2n)，最坏n-1次即O(n)
【时间】与划分是否对称有关，后者又与具体划分算法有关
最好O(nlog2n)，平衡划分
最坏O(n2)，初始序列基本有序或逆序，两个区域分别有n-1和0个元素，最大程度上的不对称发生在每一层递归上
平均O(nlog2n)，是同级别里最好的
【比较次数与初始状态】√
【移动次数与初始状态】√
【一趟排序一个关键字到达最终位置】√
【稳定性】×
【适用性】初始序列越无序越高效，可根据第i趟是否有i个元素在最终位置，再比较其是否将序列划分为为左右两部分判断是否是快排
（3）选择排序
①简单选择排序
【空间】O(1)
【时间】移动次数很少，不会超过3(n-1)，有序时最好0次；比较次数与初始序列无关，始终是n(n-1)/2次，时间复杂度始终为O(n2)
【比较次数与初始状态】× O(n2)
【移动次数与初始状态】√ O(nn2)
【一趟排序一个关键字到达最终位置】√
【稳定性】× 第i趟找到最小元素后和第i个元素交换，可能导致相对位置发生变化，顺序表交换会导致不稳定，链表插入版不会导致不稳定，若无特别说明则是顺序表
【适用性】
②堆排序
小根堆满足L(i)<=L(2i) && L(i)<=L(2i+1)，大根堆满足L(i)>=L(2i) && L(i)>=L(2i+1)
建立大根堆，输出堆顶（或者放到最后加入有序序列），将堆底元素送入堆顶，重新调整，重复以上过程直到堆中只剩一个元素
插入结点，按照完全二叉树插入在最底层最右边然后调整；删除结点，与最底层最右边结点交换再删除叶结点
筛选（调整），从无序序列所确定的完全二叉树第一个非叶结点，从右至左，从上至下依次调整。将结点p与其孩子值比较，若孩子大，与最大的孩子交换，p来到下一层重复以上操作直到孩子值都小于p
【空间】O(1)
【时间】O(nlog2n)，建堆O(n)， 只有n-1次向下调整，每次调整时间复杂度与树高有关为O(log2n)（也是插入一个、删除一个元素的复杂度）
【比较次数与初始状态】
【移动次数与初始状态】
【一趟排序一个关键字到达最终位置】√
【稳定性】× 进行筛选时有可能把后面相同关键字元素调整到前面
【适用性】在所有时间复杂度O(nlog2n)中空间复杂度最小，适合关键字较多的情况，如10000个关键字中选出10个最小
【题】小根堆，最大关键字一定存储在对应完全二叉树的叶子结点中，最后一个非叶子结点存储在⌊n/2⌋，所以最大关键字在⌊n/2⌋ +1~n之间
（4）二路归并排序
K路归并n个元素，趟数m= ⌈logkn ⌉
【空间】O(n)
【时间】O(nlog2n)，每一趟O(n)，共⌈log2n ⌉趟
【比较次数与初始状态】
【移动次数与初始状态】
【一趟排序一个关键字到达最终位置】×
【稳定性】√
【适用性】
（5）基数排序
借助“分配”和“收集”对单逻辑关键字操作，n个关键字，d为关键字位数，r为关键字基的个数，如930等三位数排序，d=3（3位），r=10（0~9）
【空间】O®
【时间】一趟分配O(n)，一趟收集O®，一共需要d趟分配和收集，时间复杂度O(d(n+r))，与初始状态无关
【比较次数与初始状态】
【移动次数与初始状态】
【一趟排序一个关键字到达最终位置】×
【稳定性】√
【适用性】关键字很多，但构成关键字的元素取值范围很小（r很小）。如果关键字取值范围也很大，如26个字母并且序列中大多数关键字关键字都不同，可以考虑使用“最高为优先”，根据最高位排成若干子序列，再对子序列进行直接插入排序