CSP-J 2020 第一轮 第 5 题：冒泡排序最少比较次数

题目

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3.     k ← FLAG -1
   4.     FLAG ← 1
   5.     for j=1 to k do
   6.         if L(j) > L(j+1) then do
   7.              L(j)  ↔ L(j+1)
   8.              FLAG ← j

对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。

选项

• A. $n^2$
• B. $n-2$
• C. $n-1$
• D. $n$

答案

C

题解

选 C．\(n-1\)。

最好的情况是数组一开始就已经按非递减顺序排列。

• 初始 FLAG = n，进入第一轮，令 k = n-1、FLAG = 1。
• for 循环中，j 从 \(1\) 到 \(n-1\)，共进行 \(n-1\) 次相邻元素比较。
• 因为数组已有序，不发生交换，FLAG 始终为 \(1\)，因此 while 循环结束。

所以最少需要比较 \(\boxed{n-1}\) 次。