NOIP 普及组初赛 · NOIP 2012 普及组初赛试题 第 8 题

使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 $1$ 个逆序对，因此序列 $5,4,3,2,1$ 需要执行（ ）次操作，才能完成冒泡排序。

这题别被冒泡排序的外壳层数迷惑，直接抓住核心：冒泡排序的本质就是交换消除逆序对，题目问几次操作，其实就是问这个序列里一共有多少个逆序对。

很多学生看到冒泡排序会下意识去数外层循环跑了几趟，或者机械地模拟交换过程，结果在完全逆序的序列里容易数错。还有的同学把冒泡和归并的交换次数搞混，或者误以为每次冒泡只消除一个逆序对（其实冒泡一趟消除的是当前元素参与的所有逆序对，但题目限定'每执行一次交换'，所以就是数对数）。最典型的坑是算出逆序对数后，没看清题目问的是'操作次数'而非'趟数'。

这道题考查的是冒泡排序与逆序对的关系。命题人挖坑的点很隐蔽：它不问你冒泡排序外层循环跑几趟，也不问你比较多少次，而是问'每执行一次交换操作系统将会减少1个逆序对'，因此交换次数等于逆序对总数。

首先要把概念讲清楚：逆序对是指序列中满足 i < j 且 a[i] > a[j] 的元素对。冒泡排序的核心操作就是相邻交换，而任意一次相邻交换恰好能消除一个逆序对，不会多也不会少。所以，要把序列排好序，需要的交换次数，就是原序列里逆序对的个数。

拿到这题，别急着模拟。序列是 5,4,3,2,1，完全逆序。对于任意两个位置 i 和 j（i < j），都有 a[i] > a[j]，也就是说，任意一对元素都构成一个逆序对。从5个元素里任选2个，组合数就是 C(5,2) = 5×4/2 = 10。所以逆序对总数是10。

既然每次交换消除1个逆序对，那要消除完这10个，自然需要10次交换。答案选C。

这里有个重要的结论要记住：对于长度为 n 的序列，完全逆序时的逆序对数就是 n(n-1)/2，也就是 C(n,2)。以后遇到类似题目，直接套公式就能秒杀，不用再去数。

考频方面，排序基础是初赛高频考点，题库共考过249题，覆盖9个级别。从历年分布看，2023年突然考了22题，2024年更是飙到51题，2025年达到57题，2026年也有50题，说明近四年排序相关题目占比极高，趋势非常明确。分赛事来看，GESP五级74题、四级39题、八级27题等，普及组初赛6题，提高组初赛12题，CSP入门级44题、提高级9题，分布很广，但GESP五级和四级是重灾区。

基于这个趋势预测：未来几年排序相关题目（包括冒泡、快速、归并等）在初赛和GESP五级、四级中仍将是必考内容，且难度可能会在基础概念上叠加一些变形（比如问最坏/最好情况、问交换次数与比较次数的关系等）。暂无足够依据预测具体的年份或题型，但准备时务必把'逆序对与交换次数'这个核心关系吃透，这是这类题的解题钥匙。