【适用性】 ②快速排序 划分思想，一趟后划分为左右两部分 【空间】递归需要栈，最好⌈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)中空间复杂度最小，适合关键字较多的情况，如 

（4）二路归并排序 【空间】O(n) 10000 个关键字中选出 10 个最小 【题】小根堆，最大关键字一定存储在对应完全二叉树的叶子结点中，最后一个非叶子结点 存储在⌊n/2⌋，所以最大关键字在⌊n/2⌋ +1~n 之间 K 路归并 n 个元素，趟数 m=⌈logkn ⌉ 【时间】O(nlog2n)，每一趟 O(n)，共⌈log2n⌉趟 【比较次数与初始状态】 【移动次数与初始状态】 【一趟排序一个关键字到达最终位置】× 【稳定性】√ 【适用性】 （5）基数排序 借助“分配”和“收集”对单逻辑关键字操作，n 个关键字，d 为关键字位数，r 为关键字基的个 数，如 930 等三位数排序，d=3（3 位），r=10（0~9） 【空间】O(r) 【时间】一趟分配 O(n)，一趟收集 O(r)，一共需要 d 趟分配和收集，时间复杂度 O(d(n+r))， 与初始状态无关 【比较次数与初始状态】 【移动次数与初始状态】 【一趟排序一个关键字到达最终位置】× 【稳定性】√ 【适用性】关键字很多，但构成关键字的元素取值范围很小（r 很小）。如果关键字取值范 围也很大，如 26 个字母并且序列中大多数关键字关键字都不同，可以考虑使用“最高为优先”， 根据最高位排成若干子序列，再对子序列进行直接插入排序