NOIP 普及 2012 第一轮 第 8 题：冒泡排序的交换次数

题目

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

选项

• A. 0
• B. 5
• C. 10
• D. 15

答案

C

题解

考点定位

本题考「冒泡与逆序对」,对应大纲 4.1.3 排序（难度【2】）。

解题过程

5,4,3,2,1 的逆序对 = C(5,2) = 10。每次交换消除恰好 1 个逆序对 ⇒ 10 次交换。

选 C。

易错提醒

① 逆序序列逆序对数 = n(n−1)/2；② 冒泡交换次数 = 逆序对数（重要等式）。