八大内部排序：稳定性、复杂度与适用场景

考点定位

本课深化 八大内部排序：稳定性、复杂度与适用场景。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

插入、希尔、冒泡、快速、选择、堆、归并、基数排序必须比较稳定性、最好/最坏复杂度、辅助空间和数据适应性。

算法推演

归并排序在合并时统计逆序：若右侧元素先于左侧剩余元素取出，新增逆序数等于左侧未合并元素个数。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

每次合并结束，输出段有序，累计逆序数恰为两个子段内部及跨段逆序之和。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：快速排序平均很快但最坏可达O(n²)且通常不稳定；归并稳定但需额外空间。

随课应用

输入n及n个整数，输出数组逆序对数量。必须用可处理较大n的O(n log n)方法。

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。