罗罗编程学习记录
本页内容 展开查看

02.5.2.1 基础排序与稳定性

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计

02.5.2.1-001 排序算法按什么维度分类?

一句话结论

按是否比较分比较排序与非比较排序;按空间分原地与非原地;按稳定性分稳定与不稳定;按平均/最坏复杂度分档;选型先看数据规模、稳定性要求与取值范围。

概念解释

  • 比较/非比较。
  • 原地/辅助空间。
  • 稳定/不稳定。

原理流程

  1. 明确排序目标。
  2. 看规模与取值。
  3. 选算法。

代码 / 图示

比较:冒泡/选择/插入/快排/归并/堆排
非比较:计数/桶/基数

常见误区

  • 误区:排序算法只看时间;正解:稳定性、空间、数据特征都要权衡。
  • 误区:非比较排序总能线性;正解:依赖取值范围假设。

追问

  • Q:比较排序下界? A:O(n log n),见 02.5.2.1-010。
  • Q:稳定排序有哪些? A:冒泡、插入、归并、计数、基数。

02.5.2.1-002 什么是排序稳定性?

一句话结论

相等元素排序后相对顺序保持不变即为稳定;不稳定排序可能交换相等元素位置;稳定性在多关键字排序(先按次关键字再按主关键字)时重要。

概念解释

  • 相等元素。
  • 相对次序。
  • 多关键字意义。

原理流程

  1. 标记相等元素原始次序。
  2. 排序后比对次序。
  3. 不变即稳定。

代码 / 图示

(2,a) (1,b) (2,c)
稳定后:(1,b) (2,a) (2,c)

常见误区

  • 误区:值相等就无所谓稳定性;正解:携带附加信息时次序有意义。
  • 误区:相邻交换一定稳定;正解:跨距交换可能不稳定。

追问

  • Q:快排稳定吗? A:不稳定,partition 跨距交换。
  • Q:怎么验证稳定性? A:相等元素带原始下标比对。

02.5.2.1-003 冒泡排序怎么做?

一句话结论

相邻元素两两比较,逆序则交换;每轮把当前最大值冒到末尾;O(n²) 时间,原地 O(1),稳定;可加提前结束标志优化已有序情形。

概念解释

  • 相邻比较。
  • 逐轮冒顶。
  • 稳定交换。

原理流程

  1. 外层轮次。
  2. 内层相邻比较交换。
  3. 无交换提前结束。

代码 / 示例

void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) { swap(a, j, j + 1); swapped = true; }
        }
        if (!swapped) break;
    }
}

常见误区

  • 误区:冒泡不稳定;正解:相邻等值不交换,稳定。
  • 误区:内层扫到末尾;正解:末尾已有序,缩短区间。

追问

  • Q:冒泡最好复杂度? A:已有序 O(n)(带标志)。
  • Q:工程常用冒泡吗? A:小规模教学用,工程少用。

02.5.2.1-004 选择排序怎么做?

一句话结论

每轮在未排序区间选最小值,交换到区间头部;O(n²) 时间,原地 O(1),不稳定;交换次数少但比较次数固定。

概念解释

  • 选最小。
  • 头部交换。
  • 跨距交换。

原理流程

  1. 外层定位置。
  2. 内层找最小下标。
  3. 交换到头部。

代码 / 示例

void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[min]) min = j;
        swap(a, i, min);
    }
}

常见误区

  • 误区:选择排序稳定;正解:跨距交换可能打乱等值次序。
  • 误区:每轮交换多次;正解:记录最小下标,一轮一次交换。

追问

  • Q:选择排序最好复杂度? A:仍 O(n²),比较无法省。
  • Q:交换次数? A:最多 n-1 次。

02.5.2.1-005 插入排序怎么做?

一句话结论

把未排序元素逐个插入左侧已排序区间的正确位置;移动较大元素后挪出空位;O(n²) 平均/最坏,最好 O(n),原地,稳定;小规模或近乎有序数据表现好。

概念解释

  • 左侧有序。
  • 找插入位。
  • 后移腾位。

原理流程

  1. 从第二个元素起。
  2. 左侧后移找空位。
  3. 插入。

代码 / 示例

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int cur = a[i], j = i - 1;
        while (j >= 0 && a[j] > cur) { a[j + 1] = a[j]; j--; }
        a[j + 1] = cur;
    }
}

常见误区

  • 误区:插入排序不稳定;正解:> 后移,等值不移动,稳定。
  • 误区:边比较边交换;正解:先存当前值,后移再插入减少写。

追问

  • Q:近乎有序为什么快? A:移动次数少,接近 O(n)。
  • Q:快排小区间优化? A:切到小规模改插入排序。

02.5.2.1-006 希尔排序是什么思路?

一句话结论

插入排序的改进:按增量分组,组内插入排序,逐步缩小增量直到 1;减少元素移动距离;突破 O(n²) 量级,复杂度依赖增量序列,不稳定。

概念解释

  • 分组增量。
  • 组内插入。
  • 增量收敛。

原理流程

  1. 选增量 gap。
  2. 隔位分组插入排序。
  3. gap 减半重复。

代码 / 图示

gap = n/2 → n/4 → … → 1

常见误区

  • 误区:希尔排序稳定;正解:跨组交换不稳定。
  • 误区:复杂度严格 O(n log n);正解:取决于增量序列,最坏可 O(n²)。

追问

  • Q:常用增量序列? A:Shell 原始、Knuth 等,具体复杂度待确认口径。
  • Q:工程常用吗? A:较少,多为概念考点。

02.5.2.1-007 常见排序稳定性对比怎么记?

一句话结论

稳定:冒泡、插入、归并、计数、基数;不稳定:选择、快排、希尔、堆排;记忆要点:相邻/同组内交换倾向稳定,跨距交换倾向不稳定。

概念解释

  • 稳定清单。
  • 不稳定清单。
  • 交换距离判断。

原理流程

  1. 看相等元素是否被跨距交换。
  2. 判定稳定性。
  3. 归类记忆。

代码 / 图示

稳定:冒泡 插入 归并 计数 基数
不稳定:选择 快排 希尔 堆排

常见误区

  • 误区:归并不稳定;正解:合并时先取左侧等值,稳定。
  • 误区:选择排序稳定;正解:跨距交换不稳定。

追问

  • Q:堆排为什么不稳定? A:堆调整跨距交换。
  • Q:多关键字排序用什么? A:稳定排序保证次关键字次序。

02.5.2.1-008 常见排序复杂度怎么对比?

一句话结论

冒泡/选择/插入平均最坏 O(n²),插入最好 O(n);快排平均 O(n log n) 最坏 O(n²);归并/堆排 O(n log n);计数/桶/基数线性 O(n+k) 或 O(n) 但有范围假设。

概念解释

  • 平方级。
  • 对数级。
  • 线性非比较。

原理流程

  1. 标注平均/最坏。
  2. 标注空间。
  3. 按场景选型。

代码 / 图示

平方:冒泡 选择 插入
对数:快排 归并 堆排
线性:计数 桶 基数

常见误区

  • 误区:快排恒 O(n log n);正解:最坏 O(n²)。
  • 误区:非比较排序无前提;正解:依赖取值范围/分布。

追问

  • Q:哪个排序最坏最稳? A:归并 O(n log n),但 O(n) 空间。
  • Q:原地对数级? A:堆排 O(1) 额外空间。

02.5.2.1-009 原地排序与非原地怎么区分?

一句话结论

原地排序只用常数辅助空间(递归栈另计),如快排、堆排、插入;非原地需额外数组,如归并 O(n);空间受限选原地,稳定需求可能接受额外空间。

概念解释

  • 辅助空间。
  • 递归栈。
  • 空间权衡。

原理流程

  1. 看是否分配结果数组。
  2. 计辅助空间。
  3. 标注口径。

代码 / 图示

原地:快排 堆排 插入
非原地:归并 O(n)

常见误区

  • 误区:快排空间 O(1);正解:递归栈 O(log n) 最坏 O(n)。
  • 误区:归并可原地;正解:原地归并复杂且常数大。

追问

  • Q:递归栈算辅助空间吗? A:算,需标注。
  • Q:链表排序额外空间? A:指针操作,节点数据不复制。

02.5.2.1-010 为什么比较排序下界是 O(n log n)?

一句话结论

比较排序的决策树叶子对应 n! 种排列,树高至少 ⌈log₂(n!)⌉ = Ω(n log n);任何比较算法最坏比较次数不低于此;非比较排序利用取值信息可突破。

概念解释

  • 决策树。
  • 排列数。
  • 信息论下界。

原理流程

  1. n! 种可能顺序。
  2. 二叉决策树叶子 ≥ n!。
  3. 树高 Ω(log n!) = Ω(n log n)。

代码 / 图示

log₂(n!) ≈ n log n

常见误区

  • 误区:存在 O(n) 比较排序;正解:比较模型下不可能突破下界。
  • 误区:冒泡 O(n²) 优于下界;正解:下界是最优可能,非所有算法达到。

追问

  • Q:归并/堆排达到下界了吗? A:O(n log n),渐近最优。
  • Q:非比较怎么突破? A:不依赖两两比较,利用值域。

02.5.2.1-011 排序算法怎么按场景选型?

一句话结论

小规模/近乎有序用插入;要求稳定且数据可额外空间用归并;通用内存排序用快排;值域集中用计数;分布均匀用桶;流式链表排序用归并;按稳定性、空间、取值范围综合选。

概念解释

  • 规模。
  • 稳定性。
  • 数据分布。

原理流程

  1. 看数据规模与有序度。
  2. 看稳定性与空间要求。
  3. 看取值范围。

代码 / 图示

小/近乎有序:插入
稳定:归并
通用:快排
值域集中:计数

常见误区

  • 误区:所有场景用快排;正解:稳定/链表/值域集中有更优选择。
  • 误区:非比较排序通用;正解:有分布与范围前提。

追问

  • Q:Java 内置排序? A:对象用稳定归并/TimSort,基本类型用快排变体(具体版本待确认)。
  • Q:外部排序? A:归并思路,见 02.5.2.4。

02.5.2.1-012 排序与二分查找是什么关系?

一句话结论

二分要求候选空间有序;排序是获得有序性的预处理;静态多次查询先排序 O(n log n),后续每次 O(log n);单次查找排序成本不划算。

概念解释

  • 有序前提。
  • 预处理成本。
  • 查询摊薄。

原理流程

  1. 先排序。
  2. 多次二分查询。
  3. 摊薄预处理。

代码 / 图示

排序 O(n log n) + k 次 O(log n)

常见误区

  • 误区:为单次二分先排序;正解:单次线性扫描更省。
  • 误区:排序后动态插入仍保持有序;正解:需平衡树/堆维护。

追问

  • Q:动态有序结构? A:BST/红黑树,见 02.4.1.2。
  • Q:Top-K 需排序吗? A:堆/快速选择可不全排序。

02.5.2.1-013 排序有哪些边界用例?

一句话结论

空数组、单元素、已有序、逆序、全相等、大量重复、含负数、极值溢出;检查提前结束、等值稳定与比较溢出。

概念解释

  • 空与最短。
  • 有序与逆序。
  • 重复与极值。

原理流程

  1. 空/单点直接返回。
  2. 有序测最好情形。
  3. 重复测稳定与退化。

代码 / 图示

[] / [1] / 升序 / 降序 / 全相等

常见误区

  • 误区:空数组访问 a[0];正解:先判长度。
  • 误区:全相等触发最坏退化;正解:重复元素看算法口径。

追问

  • Q:逆序冒泡? A:每轮全交换 O(n²)。
  • Q:极值比较溢出? A:减法比较慎用,用库比较。

02.5.2.1-014 基础排序常见错误有哪些?

一句话结论

循环边界越界、交换未封装、稳定性被等值交换破坏、提前结束标志遗漏、插入后移越界、比较方向写反;按外层轮次、内层区间、等值口径复核。

概念解释

  • 边界。
  • 等值口径。
  • 移动方向。

原理流程

  1. 核对区间边界。
  2. 核对等值是否交换。
  3. 复核移动方向。

代码 / 图示

内层区间 → 等值比较 → 后移/交换

常见误区

  • 误区:插入排序用 >= 后移破坏稳定;正解:用 >。
  • 误区:冒泡内层不缩短区间;正解:末尾已有序。

追问

  • Q:怎么自测稳定? A:等值带下标跑一遍。
  • Q:越界常见位置? A:内层 j+1 与插入 j+1。

02.5.2.1-015 基础排序复杂度怎么汇报?

一句话结论

冒泡/选择/插入平均最坏 O(n²),插入最好 O(n);辅助 O(1)(递归除外);稳定性逐项标注;非比较线性排序另列取值范围前提。

概念解释

  • 平方量级。
  • 最好情形。
  • 辅助空间。

原理流程

  1. 标注平均/最坏/最好。
  2. 标注空间。
  3. 标注稳定性。

代码 / 图示

冒泡 O(n²) 稳 / 选择 O(n²) 不稳 / 插入 O(n²) 最好 O(n) 稳

常见误区

  • 误区:只报平均复杂度;正解:面试需分最好/最坏/平均。
  • 误区:忽略稳定性;正解:选型常被追问。

追问

  • Q:插入最好为什么 O(n)? A:已有序无需后移。
  • Q:选择最好复杂度? A:比较仍 O(n²)。

02.5.2.1-016 计数排序是什么思路?

一句话结论

取值范围集中时,统计每个值出现次数,按值序回填;O(n+k) 时间 O(k) 空间,稳定;k 为值域范围;取值范围大则空间不可行。

概念解释

  • 频次数组。
  • 按值回填。
  • 值域前提。

原理流程

  1. 统计频次。
  2. 前缀和定位位置(稳定版)。
  3. 回填结果。

代码 / 示例

// 计数统计后按值顺序输出;稳定版用前缀和定位

常见误区

  • 误区:计数排序通用 O(n);正解:k 远大于 n 时空间浪费。
  • 误区:计数排序不稳定;正解:前缀和回填可保持稳定。

追问

  • Q:适用数据? A:整数且范围有限,如分数、年龄。
  • Q:负数怎么处理? A:偏移到非负下标。

02.5.2.1-017 桶排序是什么思路?

一句话结论

按范围把元素分到若干桶,桶内分别排序再合并;分布均匀时 O(n+k);依赖数据均匀分布;桶内算法自选;非比较与比较混合。

概念解释

  • 分桶。
  • 桶内排序。
  • 顺序合并。

原理流程

  1. 划分桶区间。
  2. 元素入桶。
  3. 桶内排序后拼接。

代码 / 图示

值域 → 桶 1 … 桶 k

常见误区

  • 误区:桶排序恒线性;正解:分布不均时某桶退化 O(n²)。
  • 误区:桶内不再排序;正解:桶间有序,桶内需排。

追问

  • Q:桶数怎么定? A:按值域与期望桶大小。
  • Q:外部排序桶思路? A:分块归并,见 02.5.2.4。

02.5.2.1-018 基数排序是什么思路?

一句话结论

按低位到高位(或高位到低位)逐位稳定排序,每一位用计数排序;O(d·(n+k)),d 为位数;稳定排序是多轮排序次序正确的前提。

概念解释

  • 逐位排序。
  • 稳定传递。
  • 位数轮次。

原理流程

  1. 从最低位起。
  2. 位内计数稳定排序。
  3. 逐位升到最高位。

代码 / 图示

个位 → 十位 → 百位(每轮稳定)

常见误区

  • 误区:高位优先不稳定仍可用;正解:低位优先 + 稳定才保累计次序。
  • 误区:字符串长度不一;正解:补对齐位。

追问

  • Q:基数排序适用? A:定长整数/字符串,位数有限。
  • Q:稳定性为什么关键? A:低位结果在高位轮次不被打乱。

02.5.2.1-019 非比较排序适用边界是什么?

一句话结论

元素可映射到有限离散值域(计数)、分布均匀(桶)、定长可拆位(基数);不满足时退回比较排序;非比较突破 O(n log n) 下界靠利用值域信息。

概念解释

  • 值域有限。
  • 分布假设。
  • 拆位可行。

原理流程

  1. 评估取值范围。
  2. 看分布均匀度。
  3. 选非比较或比较。

代码 / 图示

范围小:计数
分布匀:桶
定长拆位:基数

常见误区

  • 误区:浮点数直接计数;正解:需离散化或转整数位。
  • 误区:大值域用计数排序;正解:空间不可行。

追问

  • Q:对象字段排序? A:比较排序为主。
  • Q:外部大数据排序? A:归并/桶分治。

02.5.2.1-020 基础排序常见变体有哪些?

一句话结论

手写冒泡/选择/插入、稳定性判断、排序复杂度对比、多关键字排序、计数/桶/基数概念、小规模插入优化、排序后二分;主线是比较模型与稳定性、空间权衡。

概念解释

  • 基础实现。
  • 性质对比。
  • 工程优化。

原理流程

  1. 选排序算法。
  2. 标注性质。
  3. 按场景优化。

代码 / 图示

实现 → 稳定性/复杂度 → 选型

常见误区

  • 误区:变体题脱离复杂度口径;正解:先报性质再写代码。
  • 误区:多关键字用不稳定排序;正解:按次关键字到主关键字次序配稳定排序。

追问

  • Q:快排/归并/堆排详见哪页? A:02.5.2.2、02.5.2.3、02.5.2.4。
  • Q:TimSort 是什么? A:归并 + 插入优化的混合排序,具体版本待确认。