数据结构——排序（空间复杂度、时间复杂度、性能等分析）

目录

（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个字母并且序列中大多数关键字关键字都不同，可以考虑使用“最高为优先”，根据最高位排成若干子序列，再对子序列进行直接插入排序