冒泡排序 | 史玉浩的个人博客

一、引言

冒泡排序（Bubble Sort）是一种基础且直观的排序算法，它通过反复遍历待排序的数组，每次比较相邻的元素，如果顺序错误则交换它们的位置，最终较大的元素逐渐"冒泡"到数组的末尾。这个过程会重复进行，直到整个数组有序。

二、冒泡排序的原理

冒泡排序的核心思想是反复遍历数组，通过两两比较相邻的元素，将较大的元素逐渐移动到数组的末尾。每次遍历之后，未排序部分的最大值被移动到正确的位置。随着遍历的次数增加，剩下的未排序部分逐渐减少，直至整个数组有序。

算法的基本步骤如下：

从数组的起始位置开始，依次比较相邻的两个元素。
如果前一个元素大于后一个元素，则交换它们的位置。
继续向后比较相邻的元素，直到数组的末尾。
完成一次遍历后，数组的最后一个元素是最大的，固定它的位置。
重复上述过程，忽略已经排好序的元素，直到没有需要交换的元素为止。

三、时间复杂度与性能优化

冒泡排序的时间复杂度为：

最坏时间复杂度：O(n²)，当输入数组是逆序时，每次都需要进行最大次数的比较和交换。
平均时间复杂度：O(n²)，对于无序数组，通常需要反复遍历和交换。
最佳时间复杂度：O(n)，当数组已经是有序时，仅需要一次遍历即可。

为了提升性能，可以通过引入标志位优化，即在每次遍历时，若没有发生任何元素的交换，则表示数组已经有序，可以提前终止遍历。这样可以避免在数组有序时不必要的遍历。

4. 冒泡排序的完整代码展示

下面展示了使用 C++ 实现的冒泡排序代码，并引入了标志位 swapped 用于性能优化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <iostream>
#include <vector>

// 冒泡排序函数
void bubbleSort(std::vector<int>& my_array) {
    size_t length {my_array.size()};  // 获取数组的长度
    bool swapped;  // 标志位，表示本次遍历是否有元素交换
    for (size_t i {0}; i < length - 1; ++i) {  // 外层循环控制每一轮的遍历
        swapped = false;  // 每次新的一轮开始，初始化为 false
        for (size_t j {0}; j < length - i - 1; ++j) {  // 内层循环比较相邻元素
            if (my_array[j] > my_array[j + 1]) {  // 如果前一个元素大于后一个元素
                std::swap(my_array[j], my_array[j + 1]);  // 交换它们的位置
                swapped = true;  // 如果发生了交换，标志位设为 true
            }
        }
        if (!swapped) break;  // 如果本轮没有发生交换，说明数组已经有序，提前退出
    }
}

int main() {
    size_t size;  // 数组的大小
    std::cout << "Enter the size of array to be sorted from smallest to biggest: ";
    std::cin >> size;

    if (size <= 0) {  // 检查输入的数组大小是否合理
        std::cerr << "The size of array should be greater than 0." << std::endl;
        return -1;
    }

    std::vector<int> my_array(size);  // 创建大小为 size 的数组
    std::cout << "Please enter " << size << " integer numbers: ";
    for (size_t i {0}; i < size; ++i) {  // 输入数组的元素
        std::cin >> my_array[i];
    }

    bubbleSort(my_array);  // 调用冒泡排序函数对数组进行排序

    std::cout << "The array after sorted is: ";
    for (const int& num : my_array) {  // 输出排序后的数组
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

五、代码分析

主函数 main():
- 用户输入数组的大小 size，并检查输入是否合理（即数组大小必须大于 0）。
- 用户随后输入数组的元素，将这些元素存储在 std::vector<int> 容器中。
- 调用 bubbleSort() 函数对数组进行排序。
- 最后，输出排序后的数组。
bubbleSort() 函数:
- 使用双重循环实现冒泡排序。外层循环控制遍历的轮次，内层循环则是对相邻元素进行比较和交换。
- 使用 swapped 标志位来检测某轮遍历中是否发生过交换。如果某轮遍历没有交换任何元素，则说明数组已经是有序状态，此时可以提前退出循环，避免不必要的遍历。

六、冒泡排序的优缺点

优点：

冒泡排序的实现简单、直观，适合用于初学者学习基本的排序思想和算法。
对于已经接近有序的数组，可以通过标志位优化，减少排序的时间复杂度。

缺点：

冒泡排序在处理大型数组时效率较低，尤其是对于完全无序的数组，算法需要进行大量的比较和交换，导致时间复杂度为 O(n²)。
即使在优化后，冒泡排序的性能也不如一些更高效的排序算法（如快速排序、归并排序等）。

七、结论

冒泡排序虽然不是最优的排序算法，但它简单易懂，具有一定的优化空间。通过使用标志位优化，我们可以在处理已经有序或部分有序的数组时提高算法的性能。对于小规模数据，冒泡排序依然是一种可用的排序方案。

一、引言#

二、冒泡排序的原理#

三、时间复杂度与性能优化#

4. 冒泡排序的完整代码展示#

五、代码分析#

六、冒泡排序的优缺点#

七、结论#