归并排序的比较次数的数量级与序列初始状态无关,
选择排序的比较次数与序列初始状态无关。(简单选择排序的时间复杂度与序列初始状态无关)
堆排序的一趟是指 去除堆顶 把堆底最后一个元素放到堆顶进行调整到正确位置的过程
堆排序的“初始建堆”是一个动作:题目里说的“初始建堆采用自下而上逐个筛选的方法”,意思就是把这个还不符合要求的树,调整成一个真正的堆。调整完成之后,我们才叫它“初始堆”。建堆完成后的那个堆顶元素,才是选项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) | 归并排序 |
| 基本有序 | 直接插入排序、冒泡排序 |
| 关键字位数少 | 基数排序 |
| 链式存储 | 插入排序、冒泡排序、归并排序、基数排序更合适 |
| 顺序存储 | 折半插入、希尔、快排、堆排序 |
不稳定:快选堆稀 谐音:快选堆稀(快点挑选成堆,很稀少)(快速、选择、堆、希尔)
口诀:堆、希尔、快速、折半插入 不适合链表