归并排序的比较次数的数量级与序列初始状态无关,

选择排序的比较次数与序列初始状态无关。(简单选择排序的时间复杂度与序列初始状态无关)

堆排序的一趟是指 去除堆顶 把堆底最后一个元素放到堆顶进行调整到正确位置的过程

堆排序的“初始建堆”是一个动作:题目里说的“初始建堆采用自下而上逐个筛选的方法”,意思就是把这个还不符合要求的树,调整成一个真正的堆。调整完成之后,我们才叫它“初始堆”。建堆完成后的那个堆顶元素,才是选项A里说的“初始堆的堆顶元素”。

懂了懂了 堆排序 升序用大根堆 降序用小根堆 以前都理解错了 其实堆排序并没有一个输出的过程 最后堆排序完成 排好的序列依旧在存放堆的这个数据结构里 具体操作是 建好初始堆 堆顶已经是最大或最小元素 与堆底元素互换位置 再进行调整 此时固定堆底元素(最大或最小元素 类比为选择排序 每趟选出一个最大或最小) 此后就固定了这个元素 也就是这个元素已经排好序确定好最终位置了

快速排序退化到 O(n²) 的核心原因:

每一趟划分都极不均匀,一边只有0个元素,另一边有n-1个元素。

算法种类最好情况时间复杂度平均情况时间复杂度最坏情况时间复杂度空间复杂度是否稳定
直接插入排序O(n)O(n²)O(n²)O(1)是
冒泡排序O(n)O(n²)O(n²)O(1)是
简单选择排序O(n²)O(n²)O(n²)O(1)否
希尔排序—依赖于所选的增量序列,无法给出精确表达式—O(1)否
快速排序O(nlog₂n)O(nlog₂n)O(n²)O(log₂n)否
堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)否
2路归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)是
基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(r)是
算法种类最好情况时间复杂度平均情况时间复杂度最坏情况时间复杂度空间复杂度是否稳定适用性过程特征
直接插入排序O(n)O(n²)O(n²)O(1)是顺序存储、链式存储均适用;待排序序列基本有序时效率高每趟将一个元素插入到已有序子表中,前 i 个元素始终有序
折半插入排序O(nlog₂n)O(n²)O(n²)O(1)是适用于顺序存储结构(需要随机访问)利用折半查找确定插入位置,但元素移动次数不变
冒泡排序O(n)O(n²)O(n²)O(1)是顺序存储、链式存储均适用;序列基本有序时效率高每趟通过相邻元素交换确定一个最大(或最小)元素的位置
简单选择排序O(n²)O(n²)O(n²)O(1)否当记录本身信息量较大时更适合,因为交换次数少每趟从未排序区选择最大(或最小)元素,放到最终位置
希尔排序依赖增量序列依赖增量序列依赖增量序列O(1)否适用于顺序存储结构插入排序的改进,按增量分组进行直接插入排序,逐渐缩小增量
快速排序O(nlog₂n)O(n²)O(n²)O(log₂n)否适用于顺序存储结构每趟划分后确定一个枢轴元素的最终位置;采用分治思想
堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)否利用堆这种数据结构,每趟确定最大(或最小)元素的最终位置
2路归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)是顺序存储、链式存储均适用;要求稳定时优先考虑分治思想,将两个或多个有序序列合并成一个有序序列
基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(r)是关键字位数较少,可分解为多个子关键字(整数、字符串等)按关键字的每一位进行分配和收集,属于非比较排序

408选择排序算法口诀

情况推荐算法
n较小直接插入排序、简单选择排序
记录移动次数多(数据量大)简单选择排序(交换少)
n较大,要求效率高快速排序、堆排序、归并排序
要求稳定且 O(nlog₂n)归并排序
基本有序直接插入排序、冒泡排序
关键字位数少基数排序
链式存储插入排序、冒泡排序、归并排序、基数排序更合适
顺序存储折半插入、希尔、快排、堆排序

不稳定:快选堆稀 谐音:快选堆稀(快点挑选成堆,很稀少)(快速、选择、堆、希尔)

口诀:堆、希尔、快速、折半插入 不适合链表

最后修改:2026 年 07 月 30 日