📚 Bubble Sort | 冒泡排序
Bubble sort is one of the simplest sorting algorithms, often introduced early in computer science courses. It works by repeatedly stepping through a list, comparing adjacent elements and swapping them if they are in the wrong order. This process continues until no more swaps are needed, meaning the list is sorted. Although bubble sort is rarely used in practical applications due to its inefficiency on large datasets, it remains a fundamental concept for understanding algorithm analysis and appears frequently in A-Level Edexcel Computer Science examinations.
冒泡排序是最简单的排序算法之一，通常在计算机科学课程早期引入。它通过反复遍历列表、比较相邻元素并在顺序错误时交换它们来工作。这一过程持续进行，直到不再需要交换，即列表已排序。尽管冒泡排序因其在大数据集上的低效性很少用于实际应用，但它仍然是理解算法分析的基础概念，并频繁出现在 A-Level Edexcel 计算机科学考试中。
1. What is Bubble Sort? | 什么是冒泡排序？
Bubble sort is a comparison-based sorting algorithm that derives its name from the way larger elements 'bubble' up to the end of the list with each pass, similar to bubbles rising in a liquid. The algorithm repeatedly compares each pair of adjacent items and swaps them if they are in descending order. With every full pass through the list, the next largest element is placed in its correct final position, shrinking the unsorted portion by one from the right.
冒泡排序是一种基于比较的排序算法，其名称来源于较大元素在每次遍历中像液体中的气泡一样“浮”到列表末尾。该算法反复比较相邻的每一对元素，如果它们处于降序状态就进行交换。随着每一次完整遍历，下一个最大的元素被放置在它应得的最终位置，未排序部分从右侧缩减一个元素。
2. How Bubble Sort Works | 冒泡排序的工作原理
The bubble sort algorithm uses a nested loop structure. The outer loop controls the number of passes; for a list of n items, at most n-1 passes are required. In each pass, the inner loop compares adjacent elements from the beginning up to the unsorted boundary. If the element at index j is greater than the element at j+1, they are swapped. After each pass, the largest element among the unsorted portion 'bubbles up' to its correct position at the end, reducing the effective length of the next pass by one.
冒泡排序采用嵌套循环结构。外层循环控制遍历次数；对于一个包含 n 个元素的列表，最多需要 n-1 次遍历。在每次遍历中，内循环从开头到未排序的边界逐对比较相邻元素。如果索引 j 处的元素大于 j+1 处的元素，它们会被交换。每次遍历后，未排序部分中的最大元素会“冒泡”到末尾的最终正确位置，下一次遍历的有效长度因此减 1。
An important visualisation: after the first pass, the largest element is in the last position; after the second pass, the second largest is in the second-last position, and so on. This means that the unsorted region shrinks from the right as the sorted region grows.
重要的可视化过程：第一次遍历后，最大元素位于最后位置；第二次遍历后，第二大元素位于倒数第二位置，以此类推。这意味着未排序区域从右侧缩小，已排序区域不断扩大。
3. Pseudocode for Bubble Sort | 冒泡排序的伪代码
A standard pseudocode representation for bubble sort is shown below. This version performs a full n-1 passes, swapping whenever an adjacent pair is out of order.
以下是标准的冒泡排序伪代码。该版本执行完整的 n-1 次遍历，每当相邻元素对顺序错误时进行交换。
PROCEDURE bubbleSort(list)
n ← LENGTH(list)
FOR i ← 0 TO n-2
FOR j ← 0 TO n-i-2
IF list[j] > list[j+1] THEN
SWAP list[j] AND list[j+1]
ENDIF
ENDFOR
ENDFOR
ENDPROCEDURE
上面的伪代码展示了基本冒泡排序：外循环索引 i 从 0 到 n-2，内循环 j 从 0 到 n-i-2。随着 i 增大，内循环的终止位置减少，避免检查已经排好的右侧元素。交换操作通过临时变量完成。
4. Worked Example: Sorting a List | 实例：对列表进行排序
Consider sorting the list [5, 3, 8, 1, 2] using bubble sort. We will trace each pass, showing comparisons and swaps.
考虑使用冒泡排序对列表 [5, 3, 8, 1, 2] 进行排序。我们将追踪每次遍历，显示比较和交换。
Initial list: 5, 3, 8, 1, 2
初始列表： 5, 3, 8, 1, 2
ompare 8 and 2 → swap → [3, 5, 1, 2, 8]. After pass 1, 8 is in the correct final position.
第 1 次遍历：比较 5 和 3 → 交换 → [3, 5, 8, 1, 2]；比较 5 和 8 → 不交换；比较 8 和 1 → 交换 → [3, 5, 1, 8, 2]；比较 8 和 2 → 交换 → [3, 5, 1, 2, 8]。第 1 次遍历后，8 位于正确的最终位置。
d 1 → swap → [3, 1, 5, 2, 8]; compare 5 and 2 → swap → [3, 1, 2, 5, 8]. 5 is now in place.
第 2 次遍历：从 [3, 5, 1, 2, 8] 开始；比较 3 和 5 → 不交换；比较 5 和 1 → 交换 → [3, 1, 5, 2, 8]；比较 5 和 2 → 交换 → [3, 1, 2, 5, 8]。5 现在已就位。
d 1 → swap → [1, 3, 2, 5, 8]; compare 3 and 2 → swap → [1, 2, 3, 5, 8]. 3 is now in place.
第 3 次遍历：[3, 1, 2, 5, 8]；比较 3 和 1 → 交换 → [1, 3, 2, 5, 8]；比较 3 和 2 → 交换 → [1, 2, 3, 5, 8]。3 已就位。
no swap; no further swaps needed. The algorithm terminates after detecting no swaps or after the (n-1)th pass depending on implementation.
第 4 次遍历：[1, 2, 3, 5, 8]；比较 1 和 2 → 不交换；不再需要交换。根据实现方式，算法在检测到无交换后终止或完成 n-1 次遍历后终止。
5. Optimised Bubble Sort | 优化的冒泡排序
The basic bubble sort always completes n-1 passes, even if the list becomes sorted earlier. An optimised version introduces a flag (e.g., a Boolean variable 'swapped') that records whether any swap occurred during a pass. If after a full pass the flag remains false, the list is already sorted and the algorithm can exit early. This optimisation reduces the best-case time complexity from O(n²) to O(n) when the list is already sorted or nearly sorted.
基本冒泡排序总是完成 n-1 次遍历，即使列表提前变得有序。优化版本引入一个标志（例如布尔变量 'swapped'）记录在一次遍历中是否发生了交换。如果一次完整遍历后标志仍为 false，则列表已有序，算法可以提前退出。当列表已经或接近有序时，此优化将最佳情况时间复杂度从 O(n²) 降低到 O(n)。
Pseudocode with early exit:
带有提前退出的伪代码：
PROCEDURE optimisedBubbleSort(list)
n ← LENGTH(list)
FOR i ← 0 TO n-2
swapped ← FALSE
FOR j ← 0 TO n-i-2
IF list[j] > list[j+1] THEN
SWAP list[j] AND list[j+1]
swapped ← TRUE
ENDIF
ENDFOR
IF NOT swapped THEN
BREAK
ENDIF
ENDFOR
ENDPROCEDURE
此优化在每次外循环开始时将 swapped 设为 false，任何交换将其设为 true。若内循环结束后 swapped 仍为 false，则立即结束排序，从而避免不必要的遍历。
6. Time Complexity Analysis | 时间复杂度分析
er of comparisons and swaps is proportional to n², because the nested loops each run roughly n times. Without any early exit, the algorithm always performs (n-1) + (n-2) + ... + 1 ≈ n²/2 comparisons, giving a worst-case and average-case complexity of O(n²).
冒泡排序的时间复杂度通常用大 O 符号表示。对于未优化版本，最坏情况和平均情况下的比较与交换次数与 n² 成正比，因为嵌套循环各自大约运行 n 次。没有提前退出时，算法总是执行 (n-1) + (n-2) + ... + 1 ≈ n²/2 次比较，最坏和平均时间复杂度为 O(n²)。
In the best-case scenario, where the input list is already sorted, the optimised version with a swap flag performs only one pass of n-1 comparisons and no swaps, resulting in a best-case complexity of O(n). Without the flag, even a sorted list takes O(n²) time.
在最佳情况下，输入列表已经有序，采用交换标志的优化版本仅执行一次 n-1 次比较、没有交换，最佳时间复杂度为 O(n)。如果不使用标志，即使列表有序仍需 O(n²) 时间。
It is also helpful to count the number of swaps: in the worst case (reverse-sorted list), every comparison results in a swap, so the number of swaps is also O(n²). This makes bubble sort inefficient compared to more advanced algorithms.
计算交换次数也很有帮助：最坏情况下（完全逆序的列表），每次比较都导致交换，因此交换次数也是 O(n²)。这使得冒泡排序与更高级的算法相比效率低下。
7. Space Complexity | 空间复杂度
Bubble sort operates entirely in-place, using only a constant amount of additional memory for temporary variables such as the loop counters and the swap temporary variable. No extra arrays or data structures are created. Consequently, the space complexity of bubble sort is O(1), or constant extra space. This in-place nature is an advantage when memory is severely limited, although the time inefficiency usually outweighs this benefit for larger data sets.
冒泡排序完全在原位操作，仅使用常量级的额外内存，例如循环计数器和用于交换的临时变量。不创建任何额外的数组或数据结构。因此，冒泡排序的空间复杂度为 O(1)，即常量额外空间。当内存极度受限时，这种原地性是一个优势，尽管对于较大数据集，时间上的低效通常超过了这一好处。
8. Stability of Bubble Sort | 冒泡排序的稳定性
A sorting algorithm is said to be stable if it preserves the relative order of equal elements. Bubble sort is a stable sorting algorithm because swapping only occurs when list[j] is strictly greater than list[j+1], not when they are equal. Hence, equal elements are never swapped past each other, maintaining their original sequence in the sorted output. This property can be useful when sorting records by a secondary key.
如果一个排序算法能保持相等元素的相对顺序，则称该算法是稳定的。冒泡排序是稳定的排序算法，因为仅当 list[j] 严格大于 list[j+1] 时才进行交换，相等时则不会。因此相等元素永远不会相互越过，在排序输出中保留了它们的原始顺序。当按次要关键字对记录进行排序时，这一特性很有用。
9. Advantages and Disadvantages | 优缺点
• Advantage: Simplicity – bubble sort is easy to understand and implement, making it ideal for educational purposes.
• 优点：简单——冒泡排序易于理解和实现，非常适合教学目的。
• Advantage: Requires no extra memory beyond a few variables, and it is stable.
• 优点：除少量变量外不需要额外内存，且是稳定的。
• Advantage: With the early-exit flag, it can detect a sorted list quickly, achieving O(n) best-case performance.
• 优点：通过提前退出标志，可以快速检测已排序列表，实现 O(n) 最佳性能。
• Disadvantage: Very poor performance on large or random datasets; O(n²) time makes it impractical for real-world use compared to quicksort, mergesort, or even insertion sort in most cases.
• 缺点：在大型或随机数据集上性能极差；O(n²) 时间使其在大多数实际场景中与快速排序、归并排序甚至插入排序相比不切实际。
• Disadvantage: The number of swaps is high in worst-case scenarios, adding extra overhead.
• 缺点：在最坏情况下交换次数多，增加了额外开销。
10. When to Use Bubble Sort | 何时使用冒泡排序
Bubble sort is best suited for very small lists (e.g., fewer than 10 elements) or when simplicity is more important than performance. In educational contexts, it helps students grasp the concepts of traversal, comparison, and swapping, as well as nested loops. It is also occasionally used in environments where code space is extremely limited and the dataset is known to be tiny and nearly sorted.
冒泡排序最适合非常小的列表（例如少于 10 个元素），或者简单性比性能更重要的情况。在教学背景下，它帮助学生掌握遍历、比较和交换以及嵌套循环的概念。偶尔也用于代码空间极为有限、并且已知数据集很小且接近有序的环境中。
11. Comparison with Other Sorting Algorithms | 与其他排序算法的比较
Insertion sort, another O(n²) algorithm, generally outperforms bubble sort because it requires fewer swaps and comparisons on average. However, bubble sort shares the same in-place and stable characteristics. More efficient algorithms such as merge sort (O(n log n)) and quicksort (O(n log n) average) are preferred for larger data sets. In Edexcel A-Level exams, you may be asked to compare bubble sort with these algorithms in terms of time complexity, space usage, stability, and suitability for different data sizes.
插入排序是另一种 O(n²) 算法，通常优于冒泡排序，因为它在平均情况下需要的交换和比较更少。但冒泡排序同样具有原地和稳定的特性。更高效的算法，如归并排序 (O(n log n)) 和快速排序（平均 O(n log n)），更受大型数据集青睐。在 Edexcel A-Level 考试中，可能会要求从时间复杂度、空间使用、稳定性和对不同数据规模的适用性方面比较冒泡排序与这些算法。
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort (optimised) | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Not typically |
The table above summarises key characteristics. Note that bubble sort's worst-case O(n²) is the same as insertion sort's, but insertion sort often uses fewer operations due to its shifting rather than repeated swaps.
上表总结了关键特征。注意冒泡排序的最坏情况 O(n²) 与插入排序相同，但插入排序通常使用更少的操作，因为它用移位代替反复交换。
12. Exam Tips for Edexcel A-Level | Edexcel A-Level 考试提示
• Be prepared to trace bubble sort manually on a small array, clearly showing the state after each pass or after each swap. Edexcel questions often ask you to complete a trace table listing the array contents at the end of each pass.
• 准备好手动追踪小型数组上的冒泡排序，清楚显示每次遍历或每次交换之后的状态。Edexcel 的题目经常要求完成追踪表，列出每次遍历结束时的数组内容。
• Understand the role of the swap flag in optimised bubble sort and be able to explain why it reduces the best-case complexity to O(n). You may be asked to write pseudocode for the optimised version.
• 理解交换标志在优化冒泡排序中的作用，并能解释它为什么将最佳情况复杂度降低到 O(n)。可能要求为优化版本编写伪代码。
• Memorise the time and space complexities for both the standard and optimised forms. Be ready to compare bubble sort with other algorithms presented in the syllabus, such as insertion sort, merge sort, and quicksort.
• 记住标准和优化形式的时间和空间复杂度。准备将冒泡排序与教学大纲中的其他算法（如插入排序、归并排序和快速排序）进行比较。
• Pay attention to stability definitions: bubble sort is stable. Exam questions could ask you to define stability and identify which sorts are stable.
• 关注稳定性定义：冒泡排序是稳定的。考题可能要求定义稳定性并判断哪些排序是稳定的。
• When counting comparisons or swaps, remember the triangular number pattern: the total number of pairs compared in a full n-pass run is n(n-1)/2. This can help answer calculation-based questions.
• 当计算比较或交换次数时，记住三角形数字模式：完整的 n 次遍历中被比较的总对数是 n(n-1)/2。这有助于回答基于计算的问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图