5.7. 冒泡排序¶

5.7. The Bubble Sort

中文英文

冒泡排序通过多次遍历列表来进行排序。它比较相邻的项，并交换那些顺序不对的项。每次遍历列表时，将下一个最大的值放到它正确的位置。实际上，每个项都会“冒泡”到它应该在的位置。

图 1 显示了冒泡排序的第一次遍历。阴影部分的项正在被比较，以查看它们是否顺序错误。如果列表中有 \(n\) 个项，那么第一次遍历需要比较 \(n-1\) 对项。需要注意的是，一旦列表中的最大值参与了比较，它将不断被移动，直到遍历完成。

在第二次遍历开始时，最大的值已经到位。剩下 \(n-1\) 个项需要排序，这意味着会有 \(n-2\) 对项进行比较。由于每次遍历都会将下一个最大的值放到正确的位置，因此所需的总遍历次数为 \(n-1\)。完成 \(n-1\) 次遍历后，最小的项应该在正确的位置，不需要进一步处理。ActiveCode 1 显示了完整的 bubble_sort 函数。它将列表作为参数，并通过必要的交换来修改它。

在 Python 中，交换操作有些不同于大多数其他编程语言。通常，在列表中交换两个元素需要一个临时变量（一个额外的内存位置）。例如：

    temp = a_list[i]
    a_list[i] = a_list[j]
    a_list[j] = temp

这段代码会交换列表中第 \(i\) 个和第 \(j\) 个项。没有临时存储的话，某些值会被覆盖。

在 Python 中，可以进行同时赋值。语句 a, b = b, a 会同时完成两个赋值操作（见 图 2）。利用同时赋值，可以在一个语句中完成交换操作。

ActiveCode 1 中的第 5-7 行使用前面描述的三步过程进行第 \(i\) 个和第 \((i+1)\) 个项的交换。注意，我们也可以使用同时赋值来交换这些项。

以下的 activecode 示例展示了 bubble_sort 函数在上述列表上的工作情况。

活动: 5.7.1 冒泡排序实现
def bubble_sort(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                temp = a_list[j]
                a_list[j] = a_list[j + 1]
                a_list[j + 1] = temp


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)

以下动画展示了 bubble_sort 的执行过程。

有关更多细节，CodeLens 1 允许您逐步分析算法。

追踪冒泡排序
def bubble_sort(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                temp = a_list[j]
                a_list[j] = a_list[j + 1]
                a_list[j + 1] = temp


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)

为了分析冒泡排序，我们应注意无论初始列表的项如何排列，对大小为 \(n\) 的列表进行排序都将进行 \(n - 1\) 次遍历。表 1 显示了每次遍历的比较次数。总的比较次数是前 \(n - 1\) 个整数的和。回顾一下，前 \(n\) 个整数的和是 \(\frac{1}{2}n^{2} + \frac{1}{2}n\)。前 \(n - 1\) 个整数的和是 \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\)，即 \(\frac{1}{2}n^{2} - \frac{1}{2}n\)。这仍然是 \(O(n^{2})\) 次比较。在最佳情况下，如果列表已经排好序，则不会进行交换。然而，在最坏情况下，每次比较都会导致交换。平均而言，我们会进行一半的交换。

表 1: 冒泡排序每次遍历的比较次数

遍历	比较次数
1	\(n-1\)
2	\(n-2\)
3	\(n-3\)
...	...
\(n-1\)	\(1\)

冒泡排序通常被认为是最低效的排序方法，因为它必须在最终位置确定之前进行交换。这些“浪费”的交换操作是非常昂贵的。然而，由于冒泡排序会遍历整个未排序部分的列表，它有能力做一些大多数排序算法无法做到的事情。特别是，如果在遍历过程中没有进行交换，那么我们知道列表一定是排好序的。冒泡排序可以被修改为在发现列表已经排序时提前停止。这意味着对于只需要少数几次遍历的列表，冒泡排序可能具有优势，因为它会识别已排序的列表并停止。ActiveCode 2 展示了这种修改，通常称为 短冒泡排序。

活动: 5.7.2 短冒泡排序实现
def bubble_sort_short(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        exchanges = False
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                exchanges = True
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
        if not exchanges:
            break


a_list = [20, 30, 40, 90, 50, 60, 70, 80, 100, 110]
bubble_sort_short(a_list)
print(a_list)

最后，bubble_sort_short 在 CodeLens (CodeLens 2) 中的实现如下：

追踪短冒泡排序
def bubble_sort_short(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        exchanges = False
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                exchanges = True
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
        if not exchanges:
            break


a_list = [20, 30, 40, 90, 50, 60, 70, 80, 100, 110]
bubble_sort_short(a_list)
print

(a_list)

自我检测

假设你有以下数字列表需要排序：
[19, 1, 9, 7, 3, 10, 13, 15, 8, 12] 哪个列表表示冒泡排序经过三次完整遍历后的部分排序列表？

选项 a: [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
选项 b: [1, 3, 7, 9, 10, 8, 12, 13, 15, 19]
选项 c: [1, 7, 3, 9, 10, 13, 8, 12, 15, 19]
选项 d: [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]

正确答案: b

反馈 a: 这个答案表示了三次交换。一次遍历意味着你会一直交换到列表的末尾。
反馈 b: 很好
反馈 c: 冒泡排序会一直交换项直到索引位置 passnum。但记住 passnum 从列表长度减去 1 开始。
反馈 d: 你在进行插入排序，而不是冒泡排序。

The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item bubbles up to the location where it belongs.

Figure 1 shows the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are \(n\) items in the list, then there are \(n-1\) pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the list is part of a pair, it will continually be moved along until the pass is complete.

At the start of the second pass, the largest value is now in place. There are \(n-1\) items left to sort, meaning that there will be \(n-2\) pairs. Since each pass places the next largest value in place, the total number of passes necessary will be \(n-1\). After completing the \(n-1\) passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubble_sort function. It takes the list as a parameter and modifies it by exchanging items as necessary.

The exchange operation, sometimes called a swap, is slightly different in Python than in most other programming languages. Typically, swapping two elements in a list requires a temporary variable (an additional memory location). A code fragment such as

    temp = a_list[i]
    a_list[i] = a_list[j]
    a_list[j] = temp

will exchange the \(i\)-th and \(j\)-th items in the list. Without the temporary storage, one of the values would be overwritten.

In Python, it is possible to perform simultaneous assignment. The statement a, b = b, a will result in two assignment statements being done at the same time (see Figure 2). Using simultaneous assignment, the exchange operation can be done in one statement.

Lines 5--7 in ActiveCode 1 perform the exchange of the \(i\) and \((i+1)\)-th items using the three-step procedure described earlier. Note that we could also have used the simultaneous assignment to swap the items.

The following activecode example shows the complete bubble_sort function working on the list shown above.

Activity: 5.7.1 The Bubble Sort Implementation
def bubble_sort(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                temp = a_list[j]
                a_list[j] = a_list[j + 1]
                a_list[j + 1] = temp


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)

The following animation shows bubble_sort in action.

For more detail, CodeLens 1 allows you to step through the algorithm.

Tracing the Bubble Sort
def bubble_sort(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                temp = a_list[j]
                a_list[j] = a_list[j + 1]
                a_list[j + 1] = temp


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)

To analyze the bubble sort, we should note that regardless of how the items are arranged in the initial list, \(n - 1\) passes will be made to sort a list of size \(n\). Table 1 shows the number of comparisons for each pass. The total number of comparisons is the sum of the first \(n - 1\) integers. Recall that the sum of the first \(n\) integers is \(\frac{1}{2}n^{2} + \frac{1}{2}n\). The sum of the first \(n - 1\) integers is \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\), which is \(\frac{1}{2}n^{2} - \frac{1}{2}n\). This is still \(O(n^{2})\) comparisons. In the best case, if the list is already ordered, no exchanges will be made. However, in the worst case, every comparison will cause an exchange. On average, we exchange half of the time.

Table 1: Comparisons for Each Pass of Bubble Sort

Pass	Comparisons
1	\(n-1\)
2	\(n-2\)
3	\(n-3\)
...	...
\(n-1\)	\(1\)

A bubble sort is often considered the most inefficient sorting method since it must exchange items before the final location is known. These “wasted” exchange operations are very costly. However, because the bubble sort makes passes through the entire unsorted portion of the list, it has the capability to do something most sorting algorithms cannot. In particular, if during a pass there are no exchanges, then we know that the list must be sorted. A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop. ActiveCode 2 shows this modification, which is often referred to as the short bubble.

Activity: 5.7.2 The Short Bubble Sort Implementation
def bubble_sort_short(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        exchanges = False
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                exchanges = True
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
        if not exchanges:
            break


a_list = [20, 30, 40, 90, 50, 60, 70, 80, 100, 110]
bubble_sort_short(a_list)
print(a_list)

Finally, here is bubble_sort_short in CodeLens (CodeLens 2)..

Tracing the Short Bubble Sort
def bubble_sort_short(a_list):
    for i in range(len(a_list) - 1, 0, -1):
        exchanges = False
        for j in range(i):
            if a_list[j] > a_list[j + 1]:
                exchanges = True
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
        if not exchanges:
            break


a_list = [20, 30, 40, 90, 50, 60, 70, 80, 100, 110]
bubble_sort_short(a_list)
print(a_list)

Self Check

Suppose you have the following list of numbers to sort:
[19, 1, 9, 7, 3, 10, 13, 15, 8, 12] which list represents the partially sorted list after three complete passes of bubble sort?

answer a: [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
answer b: [1, 3, 7, 9, 10, 8, 12, 13, 15, 19]
answer c: [1, 7, 3, 9, 10, 13, 8, 12, 15, 19]
answer d: [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]

correct: b

feedback a: This answer represents three swaps. A pass means that you continue swapping all the way to the end of the list.
feedback b: Very Good
feedback c: A bubble sort contines to swap numbers up to index position passnum. But remember that passnum starts at the length of the list - 1.
feedback d: You have been doing an insertion sort, not a bubble sort.

最后更新: 2024年9月13日
创建日期: 2024年9月9日