← 返回资讯屏轩教育 · 行业资讯

Sorting Algorithms | 排序算法

2026-07-14 18:10 · 本文部分内容由AI辅助创作

📚 Sorting Algorithms | 排序算法

Sorting is one of the most fundamental operations in computer science. Virtually every application that processes data relies on some form of ordering to make searching, filtering and displaying information efficient. For GCSE Edexcel Computer Science, you are expected to understand how key sorting algorithms work, to trace their steps on sample data, to compare their efficiency and to write simple pseudocode for them.

排序是计算机科学中最基本的操作之一。几乎所有处理数据的应用程序都依赖某种形式的排序，以便高效地搜索、筛选和显示信息。在GCSE Edexcel计算机科学考试中，你需要理解关键排序算法的工作原理，能在示例数据上逐步跟踪它们，比较它们的效率，并为它们编写简单的伪代码。

1. What is a Sorting Algorithm? | 什么是排序算法？

A sorting algorithm is a step-by-step procedure that rearranges the elements of a list into a logical order – usually ascending (smallest to largest) or descending (largest to smallest). The input is an unsorted sequence of items, and the output is a sequence where the items follow a specified ordering rule.

排序算法是一种逐步执行的过程，它将列表中的元素重新排列成一种逻辑顺序——通常是升序（从小到大）或降序（从大到小）。输入是一个无序的项序列，输出是一个遵循指定排序规则的序列。

Sorting algorithms are studied not only because ordering data is useful, but because they illustrate key concepts like iteration, recursion, comparison and swapping. They also help us understand how the choice of algorithm can drastically affect performance as the size of the dataset grows.

研究排序算法不仅因为对数据进行排序很有用，还因为它们展示了迭代、递归、比较和交换等关键概念。它们还帮助我们理解，随着数据集规模的增长，算法的选择如何显著影响性能。

2. Why Sorting Matters | 排序为何重要

Imagine trying to find a contact in an unsorted phonebook of millions of entries - it would take forever. Once data is sorted, efficient search algorithms like binary search can be applied, reducing search time dramatically. Sorting is also essential for tasks like removing duplicates, preparing data for reports and visualizing trends.

想象一下，尝试在拥有数百万条未排序条目的电话簿中查找一个联系人——那将花费大量时间。一旦数据被排序，就可以应用二分查找等高效搜索算法，从而显著缩短搜索时间。排序对于去除重复项、为报告准备数据以及可视化趋势等任务也至关重要。

In computer systems, sorting is used in database indexing, rendering lists on websites, processing transactions and even in the lower-level routines of operating systems. Therefore, understanding sorting algorithms gives you a toolkit for making software both correct and responsive.

在计算机系统中，排序用于数据库索引、渲染网站列表、处理交易，甚至在操作系统的底层例程中。因此，理解排序算法为你提供了一个使软件既正确又响应迅速的工具包。

3. Bubble Sort – The Simple Swapper | 冒泡排序——简单的交换算法

Bubble sort is often the first sorting algorithm beginners meet. It works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The larger elements 'bubble' towards the end of the list in each pass, just like bubbles rising in water.

冒泡排序通常是初学者遇到的第一个排序算法。它的工作原理是反复遍历列表，比较每一对相邻项，如果它们的顺序错误就交换它们。在每一趟遍历中，较大的元素会像水中上升的气泡一样“冒”到列表的末尾。

The algorithm makes multiple passes through the data. During each pass, the next largest unsorted element settles into its correct final position. The process repeats until a full pass requires no swaps, which indicates the list is fully sorted.

该算法会对数据进行多次遍历。在每次遍历中，下一个最大的未排序元素会落入其正确的最终位置。此过程不断重复，直到某次完整的遍历无需进行任何交换，这表示列表已完全排序。

Bubble sort pseudocode can be described in a few steps:

冒泡排序的伪代码可以用几个步骤来描述：

4. Bubble Sort Worked Example | 冒泡排序分步示例

Let's trace bubble sort on the list [5, 3, 8, 4, 2] in ascending order. We follow the algorithm pass by pass and show the array after each swap.

让我们在列表 [5, 3, 8, 4, 2] 上按升序跟踪冒泡排序。我们逐步跟踪算法，并展示每次交换后的数组。

PassActionResulting list
1Compare 5,3 → swap; compare 5,8 → no swap; compare 8,4 → swap; compare 8,2 → swap[3, 5, 4, 2, 8]
2Compare 3,5 → no swap; compare 5,4 → swap; compare 5,2 → swap[3, 4, 2, 5, 8]
3Compare 3,4 → no swap; compare 4,2 → swap[3, 2, 4, 5, 8]
4Compare 3,2 → swap[2, 3, 4, 5, 8]
5No swaps needed; algorithm terminates[2, 3, 4, 5, 8]

Notice how the largest element (8) reaches its correct position at the end after the first pass, then the next largest (5) settles after the second pass, and so on. This is characteristic of bubble sort.

请注意，最大的元素（8）在第一趟后到达末尾的正确位置，然后第二大的元素（5）在第二趟后归位，依此类推。这是冒泡排序的典型特征。

5. Bubble Sort Efficiency and Use Cases | 冒泡排序的效率与应用场景

Bubble sort is relatively easy to understand and implement, but it is inefficient on large datasets. In the worst and average cases, it performs approximately n²/2 comparisons and swaps, where n is the number of items. This gives a time complexity of O(n²). Even in the best-case scenario (already sorted list with a swapped flag), it still needs one full pass to confirm, giving O(n).

冒泡排序相对容易理解和实现，但它在大型数据集上效率低下。在最坏和平均情况下，它大约会进行 n²/2 次比较和交换，其中 n 是项目数量。这给出了 O(n²) 的时间复杂度。即使在最好情况下（已排序列表且使用了交换标志），它仍需要一次完整遍历来确认，时间复杂度为 O(n)。

Bubble sort is rarely used in real-world applications for large data, but it serves as an excellent teaching tool for introducing algorithmic thinking. It can be useful when the list is almost sorted, or when simplicity matters more than speed.

冒泡排序在实际应用中很少用于大规模数据，但它作为引入算法思维的绝佳教学工具。当列表几乎有序，或者简单性比速度更重要时，它可能很有用。

6. Merge Sort – Divide and Conquer | 归并排序——分治法

Merge sort takes a completely different approach: it divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). Then it repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining – the sorted list.

归并排序采用了一种完全不同的方法：它将无序列表划分为 n 个子列表，每个子列表包含一个元素（含有一个元素的列表被认为是已排序的）。然后，它反复合并子列表以生成新的已排序子列表，直到只剩下一个子列表——即已排序的列表。

This 'divide and conquer' strategy is inherently recursive. The algorithm splits the problem into smaller instances of the same problem, solves them recursively, and then combines the solutions.

这种“分而治之”的策略本质上是递归的。该算法将问题拆分成同类型的小问题，递归地解决它们，然后合并这些解。

The merge step itself works by taking two sorted sublists and repeatedly picking the smaller of the two front elements to build a merged sorted list. This process is efficient because both sublists are already sorted.

合并步骤本身的工作方式是，取两个已排序的子列表，反复从两个前端元素中挑选较小的那个，以构建一个合并的已排序列表。这个过程很高效，因为两个子列表都已排序。

广告 / Sponsored

🛒
CASIO fx-991CN X 科学计算器
¥168
📱 去京东购买
京东精选

7. Merge Sort Worked Example | 归并排序分步示例

Consider the list [38, 27, 43, 3, 9, 82, 10]. Merge sort first splits it repeatedly until each sublist has one element. Then it merges them in sorted order.

考虑列表 [38, 27, 43, 3, 9, 82, 10]。归并排序首先反复拆分，直到每个子列表只有一个元素。然后按排序顺序合并它们。

Splitting phase: [38,27,43,3,9,82,10] divides into [38,27,43] and [3,9,82,10]; then further into [38] [27,43] [3,9] [82,10] and eventually into single elements: [38], [27], [43], [3], [9], [82], [10].

拆分阶段：[38,27,43,3,9,82,10] 拆分为 [38,27,43] 和 [3,9,82,10]；然后进一步拆分为 [38] [27,43] [3,9] [82,10]，最终拆分为单个元素：[38]、[27]、[43]、[3]、[9]、[82]、[10]。

82] and [10] → [10,82]; merge [3,9] and [10,82] → [3,9,10,82]; finally merge [27,38,43] and [3,9,10,82] → [3,9,10,27,38,43,82]. The list is sorted.

合并阶段（展示代表性步骤）：合并 [27] 和 [43] → [27,43]；合并 [38] 和 [27,43] → [27,38,43]；合并 [3] 和 [9] → [3,9]；合并 [82] 和 [10] → [10,82]；合并 [3,9] 和 [10,82] → [3,9,10,82]；最后合并 [27,38,43] 和 [3,9,10,82] → [3,9,10,27,38,43,82]。列表已排序。

This process can be visualised as a tree where leaves are single elements and internal nodes represent merged sublists. The depth of the tree is log₂(n), and at each level n elements are processed, giving an overall time complexity of O(n log n).

这个过程可以可视化为一棵树，其中叶子是单个元素，内部节点代表合并后的子列表。树的深度为 log₂(n)，每一层处理 n 个元素，因此总体时间复杂度为 O(n log n)。

8. Merge Sort Efficiency and Space | 归并排序的效率与空间

Merge sort has a guaranteed time complexity of O(n log n) in all cases – worst, average and best. This is significantly better than the O(n²) of bubble sort for large n. However, merge sort requires additional memory space proportional to the size of the list, because it needs temporary arrays to hold sublists during the merge step. This space complexity is O(n), which can be a disadvantage in memory-constrained environments.

归并排序在所有情况下——最坏、平均和最好——都具有 O(n log n) 的保证时间复杂度。对于较大的 n，这明显优于冒泡排序的 O(n²)。然而，归并排序需要与列表大小成比例的额外内存空间，因为它在合并步骤中需要临时数组来保存子列表。这种空间复杂度为 O(n)，在内存受限的环境中可能是一个缺点。

Merge sort is also an excellent choice when data is stored in slow-to-access structures like linked lists or files, because it accesses data sequentially, minimising expensive random access patterns. It is widely used in external sorting where data resides on disk.

当数据存储在如链表或文件等访问速度较慢的结构中时，归并排序也是一个极佳的选择，因为它按顺序访问数据，使代价高昂的随机访问模式最小化。它广泛用于数据驻留在磁盘上的外部排序。

9. Insertion Sort – Building the Sorted List | 插入排序——构建有序列表

Insertion sort builds the final sorted list one item at a time. It works similarly to how you might sort playing cards in your hand: you take one card from the unsorted pile and insert it into its correct position among the cards already sorted in your hand.

插入排序一次一项地构建最终的已排序列表。它的工作方式类似于你对手中的扑克牌进行排序：你从未排序的牌堆中取出一张牌，并将其插入到手中已排序的牌中的正确位置。

Starting from the second element, insertion sort compares the current element with the sorted portion on its left, shifting larger elements one position to the right until the correct spot is found, then inserts the current element there.

从第二个元素开始，插入排序将当前元素与其左侧已排序的部分进行比较，将较大的元素向右移动一个位置，直到找到正确的位置，然后将当前元素插入其中。

Pseudocode for insertion sort:

插入排序的伪代码：

10. Insertion Sort Worked Example | 插入排序分步示例

Using the list [5, 2, 4, 6, 1, 3], we will show how insertion sort processes each element.

使用列表 [5, 2, 4, 6, 1, 3]，我们将展示插入排序如何处理每个元素。

StepUnsorted/sorted boundaryResulting list
InitialFirst element trivially sorted[5 | 2, 4, 6, 1, 3]
i=1 (key=2)Compare 2 with sorted [5]; shift 5 right, insert 2[2, 5 | 4, 6, 1, 3]
i=2 (key=4)Compare 4 with 5; shift 5 right, insert 4 before it[2, 4, 5 | 6, 1, 3]
i=3 (key=6)6 > 5, no shifts; placed at end of sorted part[2, 4, 5, 6 | 1, 3]
i=4 (key=1)Shift 6,5,4,2 right; insert 1 at front[1, 2, 4, 5, 6 | 3]
i=5 (key=3)Shift 6,5,4 right; insert 3 after 2[1, 2, 3, 4, 5, 6]

Insertion sort is intuitive and works very efficiently for small lists or lists that are already nearly sorted. Its best-case time complexity is O(n) when no shifts are needed.

插入排序很直观，对于小型列表或几乎已排序的列表非常高效。当不需要移动元素时，其最好情况时间复杂度为 O(n)。

11. Comparing Bubble, Merge and Insertion Sort | 冒泡、归并与插入排序的比较

Each sorting algorithm has its own strengths and weaknesses. The following summary helps you choose the right one for a given scenario – and it frequently appears in exam questions.

每种排序算法都有自己的优缺点。下面的总结可帮助你针对特定场景选择合适的算法——这也是考试中常见的内容。

AlgorithmTime (worst)Time (best)SpaceStable?
Bubble SortO(n²)O(n)O(1)Yes
Merge SortO(n log n)O(n log n)O(n)Yes
Insertion SortO(n²)O(n)O(1)Yes

A stable sort preserves the relative order of equal elements. All three algorithms discussed here are stable, which is an important property when sorting by multiple keys. For the exam, remember that merge sort is the fastest for large random data, insertion sort shines on small or nearly sorted data, and bubble sort is rarely used in practice but is simple to code.

稳定排序保留相等元素的相对顺序。此处讨论的三种算法都是稳定的，这在需要按多个关键字排序时是一个重要特性。对于考试，记住归并排序对于大型随机数据最快，插入排序在小型或接近有序的数据上表现出色，而冒泡排序在实践中很少使用，但易于编写代码。

12. Exam Tips and Common Mistakes | 考试技巧与常见错误

When tackling sorting questions in the Edexcel GCSE exam, always read the question carefully. You may be asked to complete a trace table, fill in missing pieces of pseudocode, or explain why a certain algorithm is suitable for a given context.

在处理Edexcel GCSE考试中的排序问题时，务必仔细阅读题目。你可能需要完成跟踪表、填写缺失的伪代码片段，或解释为什么某种算法适合给定的上下文。