GESP 五级 · GESP 202503 C++ 五级 第 9 题

以下算法中，（ ）是不稳定的排序。

分治三步：分解（Divide）→ 解决（Conquer）→ 合并（Combine）。归并排序的关键在于合并两个有序子数组。

归并排序递归划分时，边界容易出错。注意 merge 的区间范围是左闭右开还是闭区间。

【考点】排序算法稳定性｜选择排序｜插入排序｜归并排序｜冒泡排序。命题人卡住"稳定性"概念，90%考生误以为所有排序都稳定，或混淆了算法特性。在GESP五级算法与数据结构模块中，此题专测对排序内在机制的理解，而非仅记"快排不稳定"这种碎片结论。

稳定性指相等元素相对顺序不变。选择排序每次交换非相邻元素（如2a,2b,1→1,2b,2a），直接破坏顺序；插入排序、冒泡排序只处理相邻元素，归并排序合并时保留左元素，三者均稳定。插入排序扫描时按序插入，冒泡排序只交换相邻逆序对，归并排序合并两段有序序列时相等元素取左，均不改变相对位置。

A项陷阱是"快排不稳定却不在选项"；B项陷阱是"以为插入会乱序"；C项陷阱是"合并时左优先"；D项陷阱是"冒泡只换相邻"。命题人专挖"交换非相邻元素"这一细节，背结论必错。若考生只记"选择排序不稳定"而不理解其交换机制，遇到变式（如"堆排序不稳定"）极易混淆。

若把A换成快速排序，答案仍为不稳定；若问最坏时间复杂度，选择排序与冒泡排序同为O(n²)。刷到类似题，先想"稳定性"考的是相对顺序，再看算法是否"交换非相邻元素"或"破坏原有顺序"。