Bubble Sort

Idea

Bubble Sort repeatedly compares adjacent elements and “bubbles” the larger (or smaller) one toward the end, pass by pass, until fully sorted.

冒泡排序演示

4321

下一步

Algorithm

1. Scan adjacent pairs; swap if out of order.
2. Each pass bubbles the max (or min) of the unsorted part to the end.
3. Repeat for $n-1$ passes until sorted.

Pseudo-code:

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if A[j] > A[j+1]:
            swap(A[j], A[j+1])

Complexity

• Best: $O(n)$ (already sorted, with early-exit optimization)
• Worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: stable

Exercises

Exercise 1

Sort $A = [4, 3, 2, 1]$ with bubble sort; show each pass.

参考答案

思路：每趟把最大元素“冒泡”到末尾。

步骤：

1. 初始：[4, 3, 2, 1]
2. 第 1 趟：[3, 2, 1, 4]
3. 第 2 趟：[2, 1, 3, 4]
4. 第 3 趟：[1, 2, 3, 4]

答案：如上，每一趟后最大元素归位。

Exercise 2

What are the time and space complexities of bubble sort?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n^2)$，空间 $O(1)$。

PreviousInsertion SortInsertion sort basics, algorithm flow, complexity, and practice. NextSelection SortSelection sort basics, algorithm flow, complexity, and practice.