📚 Sorting Algorithms: Bubble, Insertion, and Merge Sort Operations | 排序算法：冒泡、插入与归并排序的操作
Sorting is a fundamental operation in computer science, essential for optimizing search efficiency and data organization. This article explores three classic comparison-based sorting algorithms prescribed in the Edexcel A-Level programming syllabus: Bubble Sort, Insertion Sort, and Merge Sort. We will examine their operational mechanisms, pseudocode implementations, time and space complexities, stability, and practical use cases, enabling you to select the most appropriate algorithm for a given problem.
排序是计算机科学中的基础操作，对于优化搜索效率和数据组织至关重要。本文探讨爱德思A-Level编程考纲中规定的三种经典比较排序算法：冒泡排序、插入排序和归并排序。我们将分析它们的操作机制、伪代码实现、时间与空间复杂度、稳定性及实际应用场景，帮助你在解决问题时选择最合适的算法。
1. Introduction to Sorting | 排序简介
Sorting arranges elements of a list in a specified order, typically ascending or descending. Algorithms are evaluated by the number of comparisons and swaps they perform, which directly impacts their efficiency on different data sizes. Understanding underlying operations helps in predicting performance and resource usage.
排序将列表元素按指定顺序排列，通常是升序或降序。算法通过执行的比较和交换次数来评估，这直接影响它们在不同数据量下的效率。理解底层操作有助于预测性能和资源占用。
2. Bubble Sort Algorithm | 冒泡排序算法
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element ‘bubbles’ to the end in each pass. This process repeats until no swaps are needed, indicating the list is sorted. Its simplicity makes it easy to implement, but its quadratic time complexity limits scalability.
冒泡排序反复遍历列表，比较相邻元素，若顺序错误则交换它们。每轮遍历后，最大元素“冒泡”到末尾。重复此过程直到无需交换，表示列表已排序。其简单性易于实现，但平方级时间复杂度限制了可扩展性。
3. Bubble Sort Pseudocode and Trace | 冒泡排序伪代码与跟踪
A typical pseudocode for Bubble Sort uses a nested loop structure. The outer loop controls the number of passes, while the inner loop handles comparisons and swaps. For an array A of length n, the operations can be described as:
冒泡排序的典型伪代码使用嵌套循环结构。外层循环控制遍历次数，内层循环处理比较和交换。对于长度为n的数组A，操作可描述为：
- Set i from 0 to n-1 // 将 i 从 0 设为 n-1
- Set j from 0 to n–i-2 // 将 j 从 0 设为 n-i-2
- If A[j] > A[j+1], swap them // 若 A[j] > A[j+1]，交换之
The number of comparisons in the worst case is exactly n(n-1)/2, and the maximum number of swaps is the same. An optimised version can detect early termination if a pass makes no swaps.
最坏情况下的比较次数恰好为n(n-1)/2，最大交换次数相同。优化版本可在某轮未发生交换时提前终止。
| Pass | Array State | Swaps |
|---|---|---|
| Start | [5, 3, 8, 4, 2] | – |
| 1 | [3, 5, 4, 2, 8] | 4 |
| 2 | [3, 4, 2, 5, 8] | 2 |
| 3 | [3, 2, 4, 5, 8] | 1 |
| 4 | [2, 3, 4, 5, 8] | 1 |
4. Insertion Sort Algorithm | 插入排序算法
Insertion Sort builds the final sorted array one element at a time. It iterates through the input, taking each element and inserting it into its correct position within the already sorted portion. This method resembles sorting playing cards in hand. It is efficient for small or mostly sorted datasets.
插入排序每次取一个元素，将其插入已排序部分的正确位置，逐步构建有序数组。这种方法类似于整理手中的扑克牌。对于小型数据集或基本有序的数据，它非常高效。
5. Insertion Sort Pseudocode and Example | 插入排序伪代码与示例
The algorithm maintains a sorted sublist on the left. For each element from index 1 to n-1, it compares with elements in the sorted sublist and shifts larger values to the right, then inserts. The number of comparisons and shifts varies: at best n-1 comparisons, at worst n(n-1)/2.
该算法在左侧维护一个已排序子列表。对于从索引1到n-1的每个元素，与已排序子列表中的元素比较，将较大值右移，然后插入。比较和移动次数不等：最佳为n-1次比较，最差为n(n-1)/2。
- For i = 1 to n-1: // 对于 i 从 1 至 n-1
- key = A[i]; j = i-1 // key 暂存当前值，j 指向前一元素
- While j ≥ 0 and A[j] > key: // 当 j ≥ 0 且 A[j] 大于 key
- A[j+1] = A[j]; j = j-1 // 右移元素
- A[j+1] = key // 插入
On the array [5, 3, 8, 4, 2], the algorithm shifts elements leftward, resulting in an in-place sort that requires minimal extra memory.
在数组[5, 3, 8, 4, 2]上，算法将元素左移，实现原地排序，仅需极少额外内存。
6. Merge Sort Algorithm | 归并排序算法
Merge Sort follows a divide-and-conquer strategy. It recursively splits the unsorted list into n sublists, each containing one element (a trivially sorted list), then repeatedly merges sublists to produce new sorted sublists until only one remains. Its predictable O(n log₂ n) performance makes it highly efficient for large datasets.
归并排序采用分治策略。它递归地将无序列表拆分为n个子列表，每个只含一个元素（天然有序），然后反复合并子列表以生成新的有序子列表，直到仅剩一个。其可预测的O(n log₂ n)性能使其对大数据集极为高效。
7. Merge Sort Step-by-Step | 归并排序分步解析
The merge operation is the heart of the algorithm. It compares the first elements of two sorted halves and appends the smaller to the result, advancing the pointer in that half. This continues until one half is exhausted, then the remaining elements are appended. Merging two halves of size k each takes at most 2k-1 comparisons.
归并操作是算法的核心。它比较两个有序半区的首元素，将较小者追加到结果中，并前移该半区的指针。重复此过程直至一个半区用完，然后追加剩余元素。合并两个大小为k的半区最多需要2k-1次比较。
- Split: [5, 3, 8, 4, 2] → [5, 3, 8] and [4, 2] → further splits until singletons. // 拆分：继续拆分为单元素
- Merge singletons: [3, 5], [2, 4], [8] // 合并单元素
- Merge [3, 5] and [8] → [3, 5, 8] // 合并
- Merge [2, 4] with [3, 5, 8] → [2, 3, 4, 5, 8] // 最终合并
Recurrence relation T(n) = 2T(n/2) + O(n) solves to O(n log₂ n), which is asymptotically optimal for comparison-based sorting.
递推关系T(n) = 2T(n/2) + O(n) 解得 O(n log₂ n)，在基于比较的排序中是渐进最优的。
8. Comparing Time Complexities | 时间复杂度比较
Time complexity describes how the runtime grows with input size. Bubble Sort and Insertion Sort both have O(n²) worst-case and average-case complexities, while Merge Sort consistently achieves O(n log₂ n). Best cases differ: Bubble Sort (with early exit) and Insertion Sort can both exhibit O(n) on already sorted data, whereas Merge Sort still requires O(n log₂ n) due to mandatory splits and merges.
时间复杂度描述运行时间随输入规模的增长情况。冒泡排序和插入排序在最差和平均情况下均为O(n²)，而归并排序始终为O(n log₂ n)。最佳情况有所不同：冒泡排序（带提前终止）和插入排序对已排序数据均可呈现O(n)，而归并排序由于必须拆分和合并，仍需O(n log₂ n)。
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) |
| Merge Sort | O(n log₂ n) | O(n log₂ n) | O(n log₂ n) |
9. Comparing Space Complexities | 空间复杂度比较
Space complexity refers to the extra memory used beyond the input. Bubble Sort and Insertion Sort are in-place algorithms, requiring only O(1) auxiliary space for a few variables. Merge Sort, however, needs O(n) extra space for the temporary arrays during merging, which can be a drawback for memory-constrained environments.
空间复杂度指输入之外使用的额外内存。冒泡排序和插入排序是原地算法，仅需O(1)辅助空间存放少量变量。而归并排序在合并时需要O(n)额外空间用于临时数组，这在内存受限环境中可能成为缺点。
10. Stability of Sorting Algorithms | 排序算法的稳定性
A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Both Bubble Sort and Insertion Sort are stable because they only swap or insert when one element is strictly greater than another. Merge Sort can be implemented to be stable by ensuring that during merging, when elements from the left and right subarrays are equal, the left element is taken first. This property matters when sorting by multiple attributes.
若排序算法保持相等键值元素的相对顺序，则称其稳定。冒泡排序和插入排序是稳定的，因为它们仅在元素严格大于另一元素时才交换或插入。归并排序可通过在合并时确保相等时优先取左子数组元素来实现稳定。按多属性排序时，该性质很重要。
11. When to Use Each Algorithm | 算法选用场景
For small datasets or nearly sorted data, Insertion Sort is often the best choice due to its low overhead and O(n) best case. Bubble Sort, while educational, is rarely used in practice because its constant factors and performance are worse than Insertion Sort. Merge Sort excels for large, unsorted collections, especially when a stable sort with predictable O(n log₂ n) behaviour is required. However, its O(n) space overhead must be considered.
对于小型或近乎有序的数据集，插入排序通常是首选，因为其开销低且最佳情况为O(n)。冒泡排序虽具教学意义，但因常数因子和性能逊于插入排序，实践中很少使用。归并排序擅长处理大型无序集合，尤其需要稳定排序且可预测的O(n log₂ n)行为时，但必须考虑其O(n)空间开销。
12. Summary and Key Points | 总结与要点
Bubble Sort, Insertion Sort, and Merge Sort illustrate how algorithmic design impacts efficiency. Bubble Sort repeatedly swaps adjacent inversions; Insertion Sort builds a sorted prefix by shifting; Merge Sort recursively divides and conquers, merging with extra memory. Understanding their operations, complexities, and stability equips you to make informed decisions and to answer Edexcel examination questions on algorithm analysis.
冒泡排序、插入排序和归并排序展示了算法设计如何影响效率。冒泡排序反复交换相邻逆序对；插入排序通过移动元素构建有序前缀；归并排序递归分治，使用额外内存合并。理解它们的操作、复杂度和稳定性，有助于你做出明智决策，并解答爱德思考纲中关于算法分析的题目。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导