冒泡排序（Bubble Sort）详解

发表于 2024-10-05 分类于 Bubble Sort 阅读次数：本文字数： 11k 阅读时长 ≈ 10 分钟

冒泡排序（Bubble Sort）详解

冒泡排序是一种简单的排序算法，其工作原理是通过重复遍历要排序的数列，比较相邻的元素并在顺序错误的情况下交换它们。遍历数列的工作是重复进行的，直到没有需要交换的元素为止，这时数列已经排序完成。

冒泡排序的工作原理

比较相邻的元素：从数列的第一个元素开始，比较每一对相邻元素。如果它们的顺序错误（前一个元素大于后一个元素），就交换它们。
重复遍历：对每一对相邻元素重复上述过程，每完成一轮遍历，最大的元素会“冒泡”到数列的末尾。
减少比较范围：因为每完成一轮遍历，最大的元素已经在正确的位置，所以下一轮遍历可以忽略已经排序好的部分。
提前终止：如果在某一轮遍历中没有发生任何交换，说明数列已经有序，可以提前终止排序过程。

冒泡排序的算法步骤

初始化：设定一个标志位swapped，用于检测在一轮遍历中是否发生了交换。
外层循环：从第一元素开始，进行n-1轮遍历，其中n是数列的长度。
内层循环：在每一轮遍历中，比较相邻的元素对，并在必要时交换它们。
检查交换：如果在某一轮遍历中没有发生任何交换，说明数列已经有序，提前结束排序。
结束排序：当所有元素都按照正确的顺序排列后，排序完成。

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 - 1 - i; ++j) {
            // 如果前一个元素大于后一个元素，交换它们
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true; // 标记发生了交换
            }
        }

        // 如果一轮遍历中没有发生交换，提前结束排序
        if (!swapped) {
            break;
        }
    }
}

// 辅助函数，用于打印数组
void printArray(const std::vector<int>& arr) {
    for (const int& num : arr)
        std::cout << num << " ";
    std::cout << std::endl;
}

// 主函数示例
int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};

    std::cout << "排序前的数组: ";
    printArray(data);

    bubbleSort(data);

    std::cout << "排序后的数组: ";
    printArray(data);

    return 0;
}

输出结果：

排序前的数组: 64 34 25 12 22 11 90 
排序后的数组: 11 12 22 25 34 64 90

时间和空间复杂度分析

时间复杂度：
- 最佳情况：当数组已经有序时，只需进行一次遍历，没有交换操作，时间复杂度为O(n)。
- 平均情况：O(n²)，需要进行多次遍历和交换。
- 最坏情况：当数组是逆序排列时，需要进行最多的比较和交换，时间复杂度为O(n²)。
空间复杂度：O(1)，冒泡排序是原地排序算法，不需要额外的存储空间。
稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后相对位置不变。

冒泡排序的优化

提前终止优化：如上代码所示，通过设置swapped标志位，可以在一轮遍历中没有发生任何交换时，提前终止排序，减少不必要的比较和交换。
记录最后交换的位置：在某些实现中，可以记录最后一次交换的位置，以此来减少下一轮需要比较的元素数量，因为交换之后的元素已经有序。

优化后的代码示例如下：

#include <iostream>
#include <vector>

// 优化后的冒泡排序函数
void optimizedBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    int newn;

    do {
        newn = 0;
        for (int j = 0; j < n - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                newn = j + 1;
            }
        }
        n = newn;
    } while (newn > 0);
}

// 辅助函数和主函数同上

这种优化方式可以在某些情况下进一步减少比较次数，提高排序效率。

示例讲解

假设有一个数组[5, 1, 4, 2, 8]，我们使用冒泡排序进行排序：

第一轮遍历：

比较5和1，5 > 1，交换，数组变为[1, 5, 4, 2, 8]
比较5和4，5 > 4，交换，数组变为[1, 4, 5, 2, 8]
比较5和2，5 > 2，交换，数组变为[1, 4, 2, 5, 8]
比较5和8，5 < 8，不交换
第一轮结束，最大的元素8已在最后

第二轮遍历：

比较1和4，1 < 4，不交换
比较4和2，4 > 2，交换，数组变为[1, 2, 4, 5, 8]
比较4和5，4 < 5，不交换
比较5和8，5 < 8，不交换
第二轮结束，次大的元素5已在倒数第二位置

第三轮遍历：

比较1和2，1 < 2，不交换
比较2和4，2 < 4，不交换
比较4和5，4 < 5，不交换
由于这一轮没有发生任何交换，排序提前结束

最终排序后的数组为[1, 2, 4, 5, 8]。

冒泡排序的应用和局限性

应用场景：

冒泡排序由于实现简单，适合用于教学和理解基本排序概念。
当数据量较小时，冒泡排序的性能尚可。

局限性：

对于大规模数据，冒泡排序效率较低，不适合实际应用。
时间复杂度为O(n²)，在数据量增大时，性能急剧下降。

与其他排序算法的比较

选择排序（Selection Sort）：
- 时间复杂度同为O(n²)，但选择排序在数据交换次数上比冒泡排序少。
- 冒泡排序稳定，选择排序通常是不稳定的。
插入排序（Insertion Sort）：
- 时间复杂度同为O(n²)，但插入排序在部分有序数据上表现较好。
- 插入排序也是稳定的。
快速排序（Quick Sort）、归并排序（Merge Sort）、堆排序（Heap Sort） 等高级排序算法，时间复杂度为O(n log n)，在处理大规模数据时效率远高于冒泡排序。

深入理解C++中的冒泡排序及其在CSP-J比赛中的应用

冒泡排序（Bubble Sort）作为最基础的排序算法之一，在计算机科学的学习过程中扮演着重要角色。虽然在实际应用中由于其效率较低而不常用，但在编程竞赛（如CSP-J）中，冒泡排序仍然有其独特的价值，特别是在处理特定类型的问题时。本文将对冒泡排序进行更为详细和深入的讲解，并结合CSP-J历年真题中的实例，帮助您全面掌握这一知识点。

一、冒泡排序的深入解析

1. 冒泡排序的核心思想

冒泡排序通过重复地遍历待排序序列，比较相邻元素并在必要时交换它们，使得较大的元素逐步“冒泡”到序列的末端。这个过程重复进行，直到整个序列有序。

2. 算法步骤的详细说明

初始化标志位：用于检测在某一轮遍历中是否发生了交换操作，以判断是否提前终止排序。
外层循环（轮数控制）：通常需要进行n-1轮遍历，其中n是序列的长度。每一轮遍历确保至少一个元素被放到正确的位置。
内层循环（元素比较与交换）：在每一轮遍历中，比较相邻的元素对，如果前一个元素大于后一个元素，则交换它们。
优化策略：
- 提前终止：如果在某一轮遍历中没有发生任何交换，说明序列已经有序，可以提前结束排序。
- 记录最后交换位置：通过记录最后一次交换的位置，减少下一轮需要比较的元素数量。

3. C++中的冒泡排序实现

以下是一个更为详尽的C++实现，包括额外的优化和错误处理：

#include <iostream>
#include <vector>
#include <iomanip> // 用于格式化输出

// 冒泡排序函数，包含优化
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 - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果没有发生交换，序列已排序
        if (!swapped) {
            break;
        }
    }
}

// 辅助函数：打印数组
void printArray(const std::vector<int>& arr) {
    for (const auto& num : arr)
        std::cout << num << " ";
    std::cout << "\n";
}

// 主函数示例
int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    std::cout << "排序前的数组: ";
    printArray(data);
    
    bubbleSort(data);
    
    std::cout << "排序后的数组: ";
    printArray(data);
    
    return 0;
}

输出结果：

排序前的数组: 64 34 25 12 22 11 90 
排序后的数组: 11 12 22 25 34 64 90

4. 冒泡排序的时间与空间复杂度

时间复杂度：
- 最佳情况：O(n)（当序列已排序，仅需一次遍历，无交换）
- 平均情况：O(n²)
- 最坏情况：O(n²)
空间复杂度：O(1)（原地排序，不需要额外的存储空间）
稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后相对位置不变。

二、冒泡排序在CSP-J比赛中的应用

在CSP-J比赛中，虽然冒泡排序本身由于时间复杂度较高不常用于处理大规模数据，但其概念和变种在特定类型的问题中仍然非常实用。以下将结合CSP-J历年真题，分析冒泡排序的应用场景及解题思路。

1. 常见应用场景

小规模数据排序：当数据量较小时，冒泡排序的低常数因子和简单实现使其成为快速解决问题的选择。
检测序列有序性：通过冒泡排序的优化可以快速检测序列是否已经有序，适用于需要判断序列特性的题目。
排序相关的模拟问题：一些题目可能要求模拟排序过程，记录交换次数或特定排序步骤，此时冒泡排序的逐步交换过程非常适合。

2. CSP-J历年真题中的相关问题示例

示例题目1：交换排序次数

题目描述：
给定一个长度为n的整数序列，计算通过冒泡排序将其排序为升序所需的交换次数。

输入：
第一行包含一个整数n（1 ≤ n ≤ 1000）。
第二行包含n个整数，表示序列中的元素。

输出：
一个整数，表示冒泡排序所需的交换次数。

示例输入：

5
5 1 4 2 8

示例输出：

解题思路：
通过模拟冒泡排序的过程，记录每次交换的次数。

实现代码：

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for(auto &x: arr) std::cin >> x;
    
    int swapCount = 0;
    bool swapped;
    for(int i=0; i<n-1; ++i){
        swapped = false;
        for(int j=0; j<n-1-i; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                swapCount++;
                swapped = true;
            }
        }
        if(!swapped) break;
    }
    std::cout << swapCount;
    return 0;
}

解析：

模拟冒泡排序，遍历每一轮，比较并交换相邻元素。
每次发生交换时，swapCount递增。
最终输出交换次数。

示例题目2：优化冒泡排序后的最后交换位置

题目描述：
给定一个长度为n的整数序列，使用记录最后交换位置的优化版冒泡排序进行排序。输出每一轮遍历结束后最后交换的位置。

输入：
第一行包含一个整数n（1 ≤ n ≤ 1000）。
第二行包含n个整数，表示序列中的元素。

输出：
每一轮遍历结束后，输出最后交换的位置（从1开始计数），以空格分隔。

示例输入：

5
5 1 4 2 8

示例输出：

4 3

解题思路：
使用优化后的冒泡排序，记录每一轮交换的最后位置，并输出。

实现代码：

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for(auto &x: arr) std::cin >> x;
    
    int lastSwapPos;
    int nEnd = n;
    std::vector<int> lastPositions;
    
    while(nEnd > 0){
        lastSwapPos = 0;
        for(int j=0; j<nEnd-1; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                lastSwapPos = j + 1;
            }
        }
        if(lastSwapPos == 0) break;
        lastPositions.push_back(lastSwapPos);
        nEnd = lastSwapPos;
    }
    
    for(size_t i=0; i<lastPositions.size(); ++i){
        if(i > 0) std::cout << " ";
        std::cout << lastPositions[i];
    }
    return 0;
}

解析：

记录每轮最后一次交换的位置lastSwapPos。
更新下一轮遍历的结束位置nEnd为lastSwapPos，减少不必要的比较。
将每轮的lastSwapPos记录并最终输出。

示例题目3：逆序对的计算

题目描述：
给定一个长度为n的整数序列，计算序列中的逆序对数（即对于所有i < j，满足arr[i] > arr[j]的对数）。使用冒泡排序的交换次数来计算逆序对数。

输入：
第一行包含一个整数n（1 ≤ n ≤ 1000）。
第二行包含n个整数，表示序列中的元素。

输出：
一个整数，表示逆序对的总数。

示例输入：

5
2 3 8 6 1

示例输出：

解题思路：
冒泡排序在排序过程中交换次数等同于逆序对数。通过模拟冒泡排序，统计交换次数即可。

实现代码：

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for(auto &x: arr) std::cin >> x;
    
    int inverseCount = 0;
    bool swapped;
    for(int i=0; i<n-1; ++i){
        swapped = false;
        for(int j=0; j<n-1-i; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                inverseCount++;
                swapped = true;
            }
        }
        if(!swapped) break;
    }
    std::cout << inverseCount;
    return 0;
}

解析：

模拟冒泡排序，统计每次交换时逆序对的数量。
最终输出逆序对总数。

三、冒泡排序的变种与优化

在CSP-J比赛中，除了标准的冒泡排序，常见的变种和优化也是考察的重点。以下介绍几种常见的优化策略及其实现。

1. 鸡尾酒排序（Cocktail Shaker Sort）

鸡尾酒排序是冒泡排序的一种双向变体，能够在每一轮遍历中同时从左向右和从右向左进行元素比较和交换，减少了需要遍历的轮数。

实现代码：

#include <iostream>
#include <vector>

void cocktailShakerSort(std::vector<int>& arr){
    bool swapped = true;
    int start = 0;
    int end = arr.size() - 1;
    
    while(swapped){
        swapped = false;
        // 从左到右进行比较
        for(int i = start; i < end; ++i){
            if(arr[i] > arr[i+1]){
                std::swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
        if(!swapped) break;
        swapped = false;
        end--;
        // 从右到左进行比较
        for(int i = end-1; i >= start; --i){
            if(arr[i] > arr[i+1]){
                std::swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
        start++;
    }
}

int main(){
    std::vector<int> data = {5, 1, 4, 2, 8, 0, 3};
    cocktailShakerSort(data);
    for(auto num : data) std::cout << num << " ";
    return 0;
}

输出结果：

0 1 2 3 4 5 8

解析：

在每一轮中，先从左向右进行比较和交换，然后从右向左进行比较和交换。
这种方式可以同时将较大的元素“冒泡”到右端和较小的元素“沉淀”到左端，减少了需要的遍历轮数。

2. 冒泡排序与双指针技术结合

在某些竞赛题目中，可以将冒泡排序与双指针技术结合，用于解决复杂的排序相关问题。例如，寻找满足特定条件的元素对等。

示例题目4：找到数组中第K次交换的元素对

题目描述：
给定一个长度为n的整数序列和一个整数K，在使用冒泡排序对序列进行排序的过程中，找到第K次发生交换的元素对。如果交换次数不足K次，输出-1 -1。

输入：
第一行包含两个整数n和K（1 ≤ n ≤ 1000，1 ≤ K ≤ 10^6）。
第二行包含n个整数，表示序列中的元素。

输出：
两个整数，表示第K次交换的元素对（从小到大排列）。如果交换次数不足，输出-1 -1。

示例输入：

5 3
5 1 4 2 8

示例输出：

4 2

解题思路：

模拟冒泡排序，记录每次交换的元素对。
当交换次数达到K时，输出对应的元素对。
若遍历结束后仍未达到K，输出-1 -1。

实现代码：

#include <iostream>
#include <vector>

int main(){
    int n;
    long long K;
    std::cin >> n >> K;
    std::vector<int> arr(n);
    for(auto &x: arr) std::cin >> x;
    
    long long swapCount = 0;
    bool swapped;
    bool found = false;
    int first = -1, second = -1;
    
    for(int i=0; i<n-1 && !found; ++i){
        swapped = false;
        for(int j=0; j<n-1-i && !found; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                swapCount++;
                if(swapCount == K){
                    first = arr[j];
                    second = arr[j+1];
                    found = true;
                }
                swapped = true;
            }
        }
        if(!swapped) break;
    }
    
    if(found)
        std::cout << first << " " << second;
    else
        std::cout << "-1 -1";
    
    return 0;
}

解析：

使用swapCount记录交换次数。
在每次交换后，检查是否达到了第K次交换。
如果达到了，记录并输出交换的元素对；否则，继续排序。
最终根据是否找到输出相应结果。

四、冒泡排序的实际应用与局限性

1. 应用场景

教育与学习：冒泡排序由于其直观性，常用于教学和学习排序算法的基本概念。
小规模数据：在数据量较小的情况下，冒泡排序的低常数因子使其成为一个简单有效的选择。
特殊问题模拟：某些竞赛问题要求模拟排序过程，统计交换次数或特定排序步骤时，冒泡排序非常适用。

2. 局限性

效率低下：冒泡排序的时间复杂度为O(n²)，在处理大规模数据时效率较低。
不适合实际大规模应用：在实际应用中，通常使用更高效的排序算法，如快速排序、归并排序等。
依赖数据特性：尽管有优化，但在最坏情况下，冒泡排序仍然需要O(n²)的时间，无法利用数据的某些特性进行优化。

五、与其他排序算法的比较

在CSP-J比赛中，选择合适的排序算法至关重要。以下是冒泡排序与其他常见排序算法的对比：

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	稳定	小规模数据、教学、特定模拟问题
选择排序	O(n²)	O(1)	不稳定	需要减少交换次数的场景
插入排序	O(n²)	O(1)	稳定	部分有序数据、在线排序
快速排序	O(n log n)	O(log n)	不稳定	大规模数据、需要高效排序的场景
归并排序	O(n log n)	O(n)	稳定	需要稳定排序、处理链表等非连续存储的数据
堆排序	O(n log n)	O(1)	不稳定	不需要稳定排序、需要原地排序的大规模数据
希尔排序	介于O(n) ~ O(n²)	O(1)	不稳定	希尔排序通过分组间隔减少交换次数，适用于中等规模数据

选择排序与冒泡排序对比：

交换次数：选择排序在最坏情况下需要O(n)次交换，而冒泡排序在最坏情况下需要O(n²)次交换。
稳定性：冒泡排序是稳定的，而选择排序通常是不稳定的（但可以通过改进实现稳定性）。

插入排序的优势：

在部分有序的数据上，插入排序的效率较高，时间复杂度可接近O(n)。
插入排序也是稳定的，适用于需要保持相对顺序的场景。

高级排序算法的优势：

快速排序、归并排序等高级排序算法在处理大规模数据时表现优异，时间复杂度为O(n log n)。
这些算法在编程竞赛中应用广泛，尤其是在处理需要高效排序的复杂问题时。

六、总结

冒泡排序作为基础排序算法，虽然在效率上无法与高级排序算法相比，但其简单直观的实现和易于理解的工作原理使其成为学习排序算法的理想选择。在CSP-J等编程竞赛中，冒泡排序不仅是理解排序算法的入门工具，还在一些特定类型的问题中展现出其独特的应用价值。

通过深入理解冒泡排序的原理、优化方法以及在实际竞赛中的应用，您将能够在竞赛中更灵活地选择和应用排序算法，提升解决问题的能力。尽管冒泡排序在实际应用中局限较多，但其作为计算机科学基础知识的一部分，仍具有不可替代的重要性。

附录：更多示例题目与练习

示例题目5：冒泡排序的逆序数区间

题目描述：
给定一个长度为n的整数序列，统计在冒泡排序过程中，每一轮遍历结束后，当前序列的逆序数。

输入：
第一行包含一个整数n（1 ≤ n ≤ 1000）。
第二行包含n个整数，表示序列中的元素。

输出：
每一轮遍历结束后，输出当前序列的逆序数，以空格分隔。

示例输入：

5
5 1 4 2 8

示例输出：

3 1 0

解题思路：

在每一轮冒泡排序结束后，计算当前序列的逆序数。
使用双重循环计算逆序数。

实现代码：

#include <iostream>
#include <vector>

// 函数：计算逆序数
int countInversions(const std::vector<int>& arr){
    int inversions = 0;
    int n = arr.size();
    for(int i=0; i<n-1; ++i){
        for(int j=i+1; j<n; ++j){
            if(arr[i] > arr[j]) inversions++;
        }
    }
    return inversions;
}

int main(){
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for(auto &x: arr) std::cin >> x;
    
    std::vector<int> inversionsPerRound;
    bool swapped;
    for(int i=0; i<n-1; ++i){
        swapped = false;
        for(int j=0; j<n-1-i; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        int currentInversions = countInversions(arr);
        inversionsPerRound.push_back(currentInversions);
        if(!swapped) break;
    }
    
    for(size_t i=0; i<inversionsPerRound.size(); ++i){
        if(i > 0) std::cout << " ";
        std::cout << inversionsPerRound[i];
    }
    
    return 0;
}

解析：

每完成一轮冒泡排序，调用countInversions函数计算当前序列的逆序数，并记录。
最终输出每一轮的逆序数。

练习题目：

冒泡排序的比较次数：给定一个长度为n的整数序列，计算在冒泡排序过程中，比较的总次数。
冒泡排序的最大交换距离：在冒泡排序过程中，找到所有交换操作中，元素移动的最大距离。
逆序区间排序：给定一个长度为n的整数序列，找出最小的一个连续子序列，使得仅排序该子序列后，整个序列变为有序。使用冒泡排序的思想进行求解。

通过这些练习，您可以进一步巩固对冒泡排序及其变种的理解，提升在编程竞赛中的实战能力。