C++如何实现冒泡排序 C++冒泡排序的算法与代码示例-C++-PHP中文网

C++如何实现冒泡排序 C++冒泡排序的算法与代码示例

穿越時空

发布： 2025-08-13 18:43:01

原创

290人浏览过

冒泡排序的时间复杂度在最好情况下是o(n)，当数组已经有序时只需遍历一次；最坏情况下是o(n^2)，当数组完全逆序时需进行n-1趟比较；平均情况也是o(n^2)。优化方式包括引入swapped标志以检测是否提前完成排序，从而减少不必要的遍历。应用场景包括教学示例、数据量小或基本有序的情况，以及对性能要求不高的项目中。

C++如何实现冒泡排序 C++冒泡排序的算法与代码示例

C++实现冒泡排序，核心在于通过相邻元素的比较和交换，逐步将最大（或最小）的元素“冒泡”到序列的顶端。理解比较和交换的逻辑是关键。

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果在一趟排序中没有发生交换，说明数组已经有序
        if (swapped == false)
            break;
    }
}

int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(data);
    std::cout << "排序后的数组：\n";
    for (int i = 0; i < data.size(); i++)
        std::cout << data[i] << " ";
    std::cout << std::endl;
    return 0;
}

登录后复制

C++冒泡排序的算法与代码示例

冒泡排序的时间复杂度是多少？最好、最坏和平均情况分别是什么？

冒泡排序的时间复杂度分析起来挺有意思。最好情况下，如果数组已经是排序好的，只需要遍历一次即可确认，时间复杂度是O(n)。最坏情况下，数组是完全逆序的，需要进行n-1趟排序，每趟排序进行n-i-1次比较，时间复杂度是O(n^2)。平均情况下，时间复杂度也是O(n^2)。所以，在数据量大的时候，冒泡排序效率确实不高。

PhotoG

PhotoG是全球首个内容营销端对端智能体

121

查看详情

立即学习“C++免费学习笔记（深入）”；

如何优化冒泡排序，使其在某些情况下更快？

优化冒泡排序，一个常见的技巧是引入一个

swapped

登录后复制

标志。如果在一次完整的遍历中，没有发生任何交换，那么说明数组已经是有序的，可以直接结束排序。就像代码示例里展示的那样。这种优化对于部分有序的数组效果明显，可以提前结束排序过程。当然，即使做了优化，最坏情况下的时间复杂度仍然是O(n^2)。

冒泡排序在实际项目中的应用场景有哪些？

虽然冒泡排序效率不高，但在某些特定场景下还是有它的用武之地的。比如，当数据量很小，或者数组已经基本有序时，冒泡排序的实现简单和易于理解的优点就体现出来了。此外，冒泡排序还可以作为教学示例，帮助初学者理解排序算法的基本思想。在实际项目中，如果对性能要求不高，或者只需要对少量数据进行排序，冒泡排序也是一个可行的选择。

以上就是C++如何实现冒泡排序 C++冒泡排序的算法与代码示例的详细内容，更多请关注php中文网其它相关文章！