- 正确答案：常见的排序算法包括冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。其中稳定排序有：冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序；不稳定排序有：选择排序、希尔排序、快速排序、堆排序。 - 解答思路：判断排序算法是否稳定，核心在于考察相等元素在排序前后的相对位置是否可能被改变。若算法在比较和交换过程中，仅在严格大于（或小于）时才发生移动，且对相等元素不执行交换/重排操作，则该算法是稳定的；反之，只要存在因“非严格比较”（如 >= 或 <=）或“跳跃式移动”（如堆调整中的父子交换、快排中左右指针交叉交换、希尔的跨步交换）导致相等元素相对顺序被破坏的情况，则为不稳定。需逐个分析各算法的数据移动机制，尤其关注其最内层交换逻辑与相等元素的处理行为。 - 深度知识讲解： 1. 稳定性的定义（底层本质）：稳定性是排序算法的一个形式化性质：对于原数组中所有满足 arr[i] == arr[j] 且 i < j 的元素对，排序后 arr[i] 在逻辑上仍位于 arr[j] 之前（即其索引位置关系不变）。该性质与算法是否使用额外空间无关，而完全取决于比较与移动的语义约束。稳定性在实际工程中至关重要——例如多关键字排序（先按成绩排序，再按班级稳定排序，可保证同分学生班级顺序不变）、数据库结果集保序合并、MapReduce中Shuffle阶段的键值对聚合等场景均依赖稳定排序。 2. 各算法稳定性详解（含底层实现原理）：（1）冒泡排序（稳定）原理：相邻元素两两比较，若逆序则交换。相等元素比较结果为 false，不交换，因此相对位置恒保持。关键点：交换条件恒为 if (a[j] > a[j+1])，从不触发相等元素交换。时间复杂度：O(n²)；空间：O(1)；原地、稳定。（2）插入排序（稳定）原理：将待排序元素插入到已排序子数组的正确位置，通过后移实现腾挪。关键点：内层循环 while (j >= 0 && a[j] > key) —— 仅当 a[j] > key 时才后移；a[j] == key 时停止后移，key 插入在 a[j] 之后，保持原序。例：[2a, 1, 2b] → 插入1后为[1, 2a, 2b]；再插入2c时，比较 2b == 2c 不后移，2c 插入在 2b 后 → [1, 2a, 2b, 2c]，2a 仍在 2b 前。时间：O(n²)；空间：O(1)；原地、稳定。（3）选择排序（不稳定）原理：每轮选未排序区最小值，与未排序区首元素交换。反例：[2a, 2b, 1] → 第一轮找到 min=1，与 a[0]=2a 交换 → [1, 2b, 2a]，2b 与 2a 相对位置翻转。根本原因：交换跨越任意距离，且无相等保护逻辑（swap 操作不检查值是否相等）。时间：O(n²)；空间：O(1)；原地、不稳定。（4）希尔排序（不稳定）原理：插入排序的改进，按 gap 分组进行组内插入排序。反例：[5a, 4, 5b, 2]，gap=2 → 分组 [5a,5b], [4,2]；对第二组插入排序得 [2,4]，数组变为 [5a,2,5b,4]；再 gap=1 全局插入排序：2 插入到开头，4 与 5a 比较后插入，最终可能为 [2,4,5b,5a]，5b 在 5a 前。根本原因：跨步分组导致同一值的不同实例被分入不同子序列，后续组内排序独立进行，破坏原始次序；且组间无协调机制。时间：依赖 gap 序列，平均 O(n^1.3)；空间：O(1)；原地、不稳定。（5）归并排序（稳定）原理：分治 + 合并；合并时左右子数组均已有序，用双指针遍历，取较小者填入临时数组。关键点：合并逻辑必须为 if (L[i] <= R[j]) —— 使用 <= 而非 <，确保左半部分相等元素优先填入，从而保持 L 中 2a、2b 的原有顺序。若写成 <，则右半相等元素会抢先填入，导致不稳定。标准实现均采用 <=。时间：O(n log n)；空间：O(n)；非原地、稳定。（6）快速排序（不稳定）原理：分治，以 pivot 划分左右区间，再递归排序。反例：[3a, 2, 1, 3b]，pivot=3a；i从左找>3a（停于2？不，2<3a；继续→1；再→3b>3a），j从右找<3a（停于1），交换 3b↔1 → [3a, 2, 3b, 1]；后续操作可能导致 3b 移至 3a 前。更典型反例：[2a, 2b, 1]，pivot=2a，j 找到 1，i 停在 2a，交换 2a↔1 → [1, 2b, 2a]。根本原因：左右指针交换不区分相等与大于/小于，且 pivot 本身可能被交换到右侧，打破等值元素局部性。虽有“三路快排”（< = > 三区间）可保持等值块内部稳定，但标准二路快排必不稳定。时间：平均 O(n log n)，最坏 O(n²)；空间：O(log n)（递归栈）；原地、不稳定。（7）堆排序（不稳定）原理：建最大堆，重复取堆顶与末尾交换，然后 heapify。反例：[2a, 2b, 1] → 建堆过程（自底向上 sift-down）：1 与父 2b 比较不交换；再与父 2a 比较，因 1<2a 不交换；堆为 [2a,2b,1]；取 2a 与 1 交换 → [1,2b,2a]；heapify 根 1：与较大子节点 2b 交换 → [2b,1,2a]；再与子节点比较，最终排序为 [1,2a,2b] 或 [1,2b,2a]，取决于 heapify 路径。但关键在第一次交换就已将 2a（原首）与末尾 1 交换，使 2b 相对提前。根本原因：堆调整（sift-down）中父子交换不检查相等性，且全局交换（swap(arr[0],arr[n-1])）强制打乱原始索引关系。时间：O(n log n)；空间：O(1)；原地、不稳定。（8）计数排序（稳定）原理：统计每个值出现频次，利用前缀和确定每个值的输出区间，逆序遍历原数组填充结果。关键点：“逆序遍历”是稳定性的核心：对相同值 k，后出现的元素在结果数组中被填入更靠后的下标（因 cnt[k] 递减），从而保持输入中相对顺序。伪代码关键段： for i = n-1 downto 0: k = A[i] pos = C[k] - 1 // C[k] 是前缀和，表示值k最后一个位置 B[pos] = A[i] C[k] = C[k] - 1 若正序遍历，则先出现的元素填在后面，导致倒序，故必须逆序。时间：O(n + k)；空间：O(n + k)；非原地、稳定。（9）桶排序（稳定，前提：桶内排序稳定）原理：将值域划分为若干桶，分配元素，桶内排序，顺序收集。稳定性保障：只要桶内排序算法稳定（如用插入排序或归并排序），且分配过程不改变同桶内元素顺序（通常按原数组顺序追加），则整体稳定。若桶内用快排则整体不稳定。时间：平均 O(n + k)，k为桶数；空间：O(n + k)；非原地、条件稳定。（10）基数排序（稳定）原理：按位（LSD或MSD）调用稳定排序（通常是计数排序）作为子过程。关键点：必须使用稳定排序作为子过程，且从最低位开始（LSD）。因为高位相同则由低位决定顺序，若低位排序不稳定，则相同高位组内顺序混乱，无法保证最终全序。LSD + 稳定子排序 = 整体稳定。时间：O(d*(n+k))，d为位数；空间：O(n+k)；非原地、稳定。 - 扩展知识： - 稳定性不可“修复”：无法通过对不稳定算法增加额外键（如索引）来使其稳定而不改变其本质复杂度；但可在应用层模拟（如给每个元素附加初始下标，排序键变为 (value, index)），此时时间空间开销增加。 - 工程权衡：STL std::sort 是 introsort（快排+堆排+插排混合），不稳定；std::stable_sort 通常实现为归并排序（或优化的缓存友好型归并），稳定但耗内存。Java Arrays.sort 对对象数组使用 Timsort（归并+插入混合，稳定），对基本类型用双轴快排（不稳定）——正是因基本类型无“相等但需区分”的语义需求。 - 理论极限：比较排序的稳定版本时间复杂度下界仍是 Ω(n log n)，与不稳定版本相同；但非比较排序（计数、基数）可突破此限，且天然支持稳定。 - 伪代码示例（归并排序合并段，体现稳定性）： function merge(L, R): i = 0, j = 0, k = 0 result = new array of size len(L)+len(R) while i < len(L) and j < len(R): if L[i] <= R[j]: // 注意是 <=，非 < result[k] = L[i] i = i + 1 else: result[k] = R[j] j = j + 1 k = k + 1 // 复制剩余 while i < len(L): result[k] = L[i]; i++; k++ while j < len(R): result[k] = R[j]; j++; k++ return result

美团面经 Java开发

全站热榜

创作者周榜