冒泡排序(Bubble Sort)

冒泡排序（英语：Bubble Sort，又称泡式排序）是一种简单的排序算法。
它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。
该算法名字的由来是因为较小的元素会经由交换慢慢“浮”到数列的顶端。

---

算法特点

项目	说明
类别	排序算法
数据结构	数组
平均时间复杂度	O(n²)
最坏时间复杂度	O(n²)
最优时间复杂度	O(n)（优化后）
空间复杂度	O(1)（原地排序）
稳定性	稳定

---

工作原理

1. 比较相邻元素：如果第一个比第二个大，就交换它们。
2. 从头到尾重复上述操作，直到最后一个元素，此时最后一个元素为最大值。
3. 缩小范围：对剩余的元素重复以上步骤（不再包含已排序的末尾元素）。
4. 结束条件：当一轮遍历中没有发生任何交换时，排序完成。

由于其简单性，冒泡排序常用于程序设计入门教学。但在处理大量数据时效率较低。

---

伪代码

function bubble_sort(array, length):
    for i from 0 to length-2:
        for j from 0 to length-2-i:
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])

助记形式：

i ∈ [0, N-1)       // 循环 N-1 遍
j ∈ [0, N-1-i)     // 每遍处理的无序部分
swap(j, j+1)       // 两两比较并交换

---

动画演示

---

多语言实现示例

C 语言

void bubbleSort(int arr[], int len) {
    int i, j, temp;
    _Bool exchanged = true;

    for (i = 0; exchanged && i < len - 1; i++) {
        exchanged = false;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                exchanged = true;
            }
        }
    }
}

---

C++

template<typename T>
void bubble_sort(T arr[], int len) {
    for (int i = 0; i < len - 1; i++)
        for (int j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);
}

---

Python

def bubble_sorted(iterable):
    new_list = list(iterable)
    n = len(new_list)
    for i in range(n-1):
        for j in range(n-1-i):
            if new_list[j] > new_list[j+1]:
                new_list[j], new_list[j+1] = new_list[j+1], new_list[j]
    return new_list

# 示例
testlist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
print('sorted:', bubble_sorted(testlist))

---

JavaScript

Array.prototype.bubble_sort = function() {
    for (let i = 0; i < this.length - 1; i++) {
        for (let j = 0; j < this.length - 1 - i; j++) {
            if (this[j] > this[j + 1]) {
                [this[j], this[j + 1]] = [this[j + 1], this[j]];
            }
        }
    }
    return this;
};

let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
console.log(num.bubble_sort());

---

Java

private int[] bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return array;
}