Bubble Sort: Algorithm, Tracing and Complexity | 冒泡排序：算法、跟踪与复杂度

📚 Bubble Sort: Algorithm, Tracing and Complexity | 冒泡排序：算法、跟踪与复杂度

Bubble sort is one of the simplest comparison-based sorting algorithms covered in Edexcel A-Level Computer Science. It repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process ‘bubbles’ the largest remaining value to the end of the list after each pass. Although it is not efficient for large datasets, it is an excellent introduction to sorting, correctness and algorithm analysis.

冒泡排序是 Edexcel A-Level 计算机科学中最简单的基于比较的排序算法之一。它重复比较相邻元素，如果顺序错误就交换。每完成一遍，当前未排序部分的最大值就会“冒泡”到列表末尾。虽然它对于大数据集效率不高，但它是学习排序、正确性和算法分析的绝佳入门内容。

1. What is Bubble Sort? | 什么是冒泡排序？

Bubble sort is a comparison sort that works by repeatedly stepping through a list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The name comes from the way smaller elements ‘bubble’ to the front and larger elements ‘sink’ to the end. It is a stable, in-place algorithm that requires no extra memory beyond a single temporary variable for swapping.

冒泡排序是一种比较排序，它通过反复遍历列表，比较每一对相邻元素，如果顺序错误则交换它们。其名称源于较小元素“冒泡”到前面，而较大元素“下沉”到末尾。它是一种稳定的原地排序算法，除了用于交换的单个临时变量外，不需要额外内存。

2. Core Mechanism and Passes | 核心机制与遍历趟数

A pass is one complete scan through the list from left to right. In each pass, adjacent pairs are compared and swapped if A[i] > A[i+1] for ascending order. After the first pass, the largest element is guaranteed to be in its final position at the end. Therefore, the next pass only needs to scan the first n-1 elements. In general, after k passes, the last k elements are sorted.

一趟是从左到右完整扫描列表的过程。在每一趟中，如果是升序排列，当 A[i] > A[i+1] 时交换相邻元素。第一趟结束后，最大的元素保证位于最后的位置。因此下一趟只需扫描前 n-1 个元素。一般来说，经过 k 趟后，最后 k 个元素已经排好。

3. Step-by-Step Trace Example | 分步跟踪示例

Trace the bubble sort on the list [5, 1, 4, 2, 8]. In Pass 1, compare 5 and 1, swap to get [1, 5, 4, 2, 8]; compare 5 and 4, swap to get [1, 4, 5, 2, 8]; compare 5 and 2, swap to get [1, 4, 2, 5, 8]; compare 5 and 8, no swap. End of Pass 1: [1, 4, 2, 5, 8], with 8 fixed in the last position.

以列表 [5, 1, 4, 2, 8] 为例跟踪冒泡排序。第 1 趟：比较 5 和 1，交换得到 [1, 5, 4, 2, 8]；比较 5 和 4，交换得到 [1, 4, 5, 2, 8]；比较 5 和 2，交换得到 [1, 4, 2, 5, 8]；比较 5 和 8，不交换。第 1 趟结束：[1, 4, 2, 5, 8]，最大值 8 固定在最后一个位置。

In Pass 2, only the first four elements need to be scanned: [1, 4, 2, 5]. Compare 1 and 4, no swap; compare 4 and 2, swap to get [1, 2, 4, 5, 8]; compare 4 and 5, no swap. End of Pass 2: [1, 2, 4, 5, 8], with 5 and 8 fixed. In Pass 3, the unsorted portion [1, 2, 4] contains no out-of-order pairs, so no swaps occur. If the algorithm is optimised with an early exit flag, it will stop here.

第 2 趟只需扫描前四个元素：[1, 4, 2, 5]。比较 1 和 4，不交换；比较 4 和 2，交换得到 [1, 2, 4, 5, 8]；比较 4 和 5，不交换。第 2 趟结束：[1, 2, 4, 5, 8]，5 和 8 已固定。第 3 趟，未排序部分 [1, 2, 4] 中没有乱序对，因此不发生交换。如果算法使用提前退出标志进行优化，它会在这里停止。

4. Pseudocode for Bubble Sort | 冒泡排序的伪代码

Below is the standard pseudocode for an optimised bubble sort that stops early if no swaps occur in a pass. The outer loop controls the number of passes, while the inner loop performs adjacent comparisons within the unsorted portion.

下面是优化版冒泡排序的标准伪代码，如果一趟中没有发生交换则提前停止。外层循环控制趟数，内层循环在未排序部分执行相邻比较。

PROCEDURE BubbleSort(A)
n ← LENGTH(A)
FOR i ← 0 TO n-2 DO
swapped ← FALSE
FOR j ← 0 TO n-i-2 DO
IF A[j] > A[j+1] THEN
SWAP A[j], A[j+1]
swapped ← TRUE
ENDIF
ENDFOR
IF swapped = FALSE THEN
BREAK
ENDIF
ENDFOR
ENDPROCEDURE

The variable i counts completed passes, and j iterates through the unsorted part. If after a full pass swapped is still FALSE, the list is sorted and the algorithm terminates early. This reduces the best-case time to O(n).

变量 i 统计已完成的趟数，j 遍历未排序部分。如果一趟结束后 swapped 仍为 FALSE，则列表已有序，算法提前终止。这使最好情况时间复杂度降为 O(n)。

5. Time Complexity Analysis | 时间复杂度分析

In the worst case and average case, bubble sort makes approximately (n-1) + (n-2) + … + 1 = n(n-1)/2 comparisons. This is O(n²). In the best case, when the input is already sorted, an optimised bubble sort makes only one pass with n-1 comparisons and no swaps, giving O(n). The number of swaps is also O(n²) in the worst case because each comparison may require a swap.

在最坏和平均情况下，冒泡排序大约进行 (n-1) + (n-2) + … + 1 = n(n-1)/2 次比较，因此时间复杂度为 O(n²)。在最好情况下，即输入已经有序时，优化版冒泡排序只需一趟，进行 n-1 次比较且无交换，时间复杂度为 O(n)。最坏情况下交换次数也是 O(n²)，因为每次比较都可能需要交换。

6. Space Complexity and Stability | 空间复杂度与稳定性

Bubble sort is an in-place algorithm because it only requires a constant amount of extra space, O(1), for a temporary variable during swapping. It is a stable sort: equal elements are never swapped, so their relative order is preserved. This property is important when sorting records by one field while preserving order by another.

冒泡排序是原地算法，因为交换时只需要常量级额外空间 O(1) 来存储临时变量。它是一种稳定排序：相等的元素不会被交换，因此它们的相对顺序得以保留。当按一个字段对记录排序，同时又要保持另一字段的顺序时，这一性质非常重要。

7. Optimising Bubble Sort with Early Exit | 利用提前退出优化冒泡排序

The standard unoptimised bubble sort always performs n-1 passes even if the list becomes sorted early. By using a flag such as swapped, the algorithm can detect that no swaps were made in a complete pass and terminate immediately. This is the version usually expected in Edexcel examination questions. It does not improve the worst-case complexity, but it can dramatically reduce the number of passes for nearly sorted data.

未经优化的标准冒泡排序总是执行 n-1 趟，即使列表提前已经有序。通过使用诸如 swapped 这样的标志，算法可以检测到一趟中没有发生交换并立即终止。这正是 Edexcel 考试题目中通常期望的版本。它不会改善最坏情况复杂度，但可以大幅减少

Published by TutorHao | A-Level Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）