C++ 冒泡排序与选择排序

📚 排序算法概述

什么是排序？

排序（Sorting）是将一组数据按照特定顺序（升序或降序）重新排列的过程。排序是计算机科学中最基本的算法之一。

✅ 升序排序：从小到大（1, 2, 3, 4, 5）
✅ 降序排序：从大到小（5, 4, 3, 2, 1）
✅ 应用场景：成绩排名、商品排序、数据检索
💡 学习价值：理解算法思想，为高级算法打基础

💡 为什么要学习多种排序算法？
• 不同算法有不同的性能特点
• 适合不同的数据规模和场景
• 理解算法设计思想和优化技巧

冒泡排序（Bubble Sort）

核心思想：重复遍历数组，比较相邻元素，如果顺序错误就交换它们。每一轮遍历会将最大的元素"冒泡"到末尾。

// 冒泡排序可视化过程
// 原始数组：[5, 3, 8, 1, 2]

// 第1轮：将最大值8移到末尾
// [5, 3, 8, 1, 2] → 比较5和3，交换
// [3, 5, 8, 1, 2] → 比较5和8，不交换
// [3, 5, 8, 1, 2] → 比较8和1，交换
// [3, 5, 1, 8, 2] → 比较8和2，交换
// [3, 5, 1, 2, |8|] ← 8已就位

// 第2轮：将次大值5移到倒数第二
// [3, 5, 1, 2, |8|] → 比较3和5，不交换
// [3, 5, 1, 2, |8|] → 比较5和1，交换
// [3, 1, 5, 2, |8|] → 比较5和2，交换
// [3, 1, 2, |5, 8|] ← 5已就位

// 继续直到所有元素就位...

选择排序（Selection Sort）

核心思想：每一轮从未排序部分找到最小（或最大）元素，放到已排序部分的末尾。

// 选择排序可视化过程
// 原始数组：[5, 3, 8, 1, 2]

// 第1轮：找到最小值1，放到位置0
// [5, 3, 8, 1, 2] → 最小值是1（位置3）
// [1, |3, 8, 5, 2|] ← 1已就位

// 第2轮：在剩余部分找到最小值2，放到位置1
// [1, 3, 8, 5, 2] → 最小值是2（位置4）
// [1, 2, |8, 5, 3|] ← 2已就位

// 第3轮：在剩余部分找到最小值3，放到位置2
// [1, 2, 8, 5, 3] → 最小值是3（位置4）
// [1, 2, 3, |5, 8|] ← 3已就位

// 继续直到所有元素就位...

⚙️ 算法实现

冒泡排序完整实现

#include <iostream>
using namespace std;

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 外层循环：控制轮数
        for (int j = 0; j < n - 1 - i; j++) {  // 内层循环：比较相邻元素
            if (arr[j] > arr[j + 1]) {           // 如果前一个大于后一个
                // 交换两个元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前：";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "排序后：";
    printArray(arr, n);
    
    return 0;
}

选择排序完整实现

#include <iostream>
using namespace std;

// 选择排序函数
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {      // 外层循环：控制已排序部分
        int minIndex = i;                    // 假设当前位置是最小值
        
        // 内层循环：在未排序部分找最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;                 // 更新最小值索引
            }
        }
        
        // 将最小值交换到已排序部分的末尾
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前：";
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    cout << "排序后：";
    printArray(arr, n);
    
    return 0;
}

🎮 互动实验：排序演示

输入数组元素，查看两种排序的过程

数组元素（用逗号分隔）：

输入数组后点击按钮...

🛠️ 算法比较

两种排序的对比

特性	冒泡排序	选择排序
最好时间复杂度	O(n)（优化后）	O(n²)
平均时间复杂度	O(n²)	O(n²)
最坏时间复杂度	O(n²)	O(n²)
空间复杂度	O(1)	O(1)
稳定性	稳定	不稳定
交换次数	较多	较少（最多n-1次）

💡 关键区别：
• 冒泡排序：通过不断交换相邻元素来排序，可以提前终止
• 选择排序：每轮只交换一次，交换次数少，但无法提前终止
• 两者都是O(n²)，适合小规模数据

冒泡排序的优化

// 优化1：添加标志位，如果没有交换说明已排序
void optimizedBubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // 标志位
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // 如果没有交换，说明已经有序，提前退出
        if (!swapped) {
            break;
        }
    }
}

// 优化2：记录最后交换位置，减少比较范围
void betterBubbleSort(int arr[], int n) {
    int lastSwapPos = n - 1;
    
    while (lastSwapPos > 0) {
        int currentSwapPos = 0;
        
        for (int j = 0; j < lastSwapPos; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                currentSwapPos = j;
            }
        }
        
        lastSwapPos = currentSwapPos;
    }
}

实际应用：学生成绩排序

#include <iostream>
#include <string>
using namespace std;

struct Student {
    string name;
    double score;
};

// 按成绩降序排序（冒泡排序）
void sortByScore(Student students[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (students[j].score < students[j + 1].score) {
                // 交换整个结构体
                Student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

int main() {
    Student students[] = {
        {"张三", 85.5},
        {"李四", 92.0},
        {"王五", 78.5},
        {"赵六", 95.0}
    };
    int n = 4;
    
    cout << "=== 成绩排名 ===" << endl;
    sortByScore(students, n);
    
    for (int i = 0; i < n; i++) {
        cout << (i+1) << ". ";
        cout << students[i].name << ": ";
        cout << students[i].score << "分" << endl;
    }
    
    return 0;
}

🚀 性能分析与优化

时间复杂度详细分析

// 冒泡排序的比较次数
// 第1轮：n-1 次比较
// 第2轮：n-2 次比较
// ...
// 第n-1轮：1 次比较

// 总比较次数 = (n-1) + (n-2) + ... + 1
//            = n(n-1)/2
//            ≈ n²/2
// 所以时间复杂度 = O(n²)

// 示例：n=5时
// 比较次数 = 4 + 3 + 2 + 1 = 10次
// n=100时
// 比较次数 = 99 + 98 + ... + 1 = 4950次

数据规模n	比较次数	近似计算时间
10	45	瞬间
100	4,950	瞬间
1,000	499,500	几毫秒
10,000	49,995,000	几百毫秒
100,000	约50亿	几分钟

性能测试对比

#include <iostream>
#include <chrono>
#include <cstdlib>
using namespace std;
using namespace chrono;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    const int SIZE = 5000;
    int arr1[SIZE], arr2[SIZE];
    
    // 生成随机数组
    for (int i = 0; i < SIZE; i++) {
        arr1[i] = arr2[i] = rand() % 10000;
    }
    
    // 测试冒泡排序
    auto start1 = high_resolution_clock::now();
    bubbleSort(arr1, SIZE);
    auto end1 = high_resolution_clock::now();
    auto duration1 = duration_cast(end1 - start1);
    
    // 测试选择排序
    auto start2 = high_resolution_clock::now();
    selectionSort(arr2, SIZE);
    auto end2 = high_resolution_clock::now();
    auto duration2 = duration_cast(end2 - start2);
    
    cout << "数据规模：" << SIZE << endl;
    cout << "冒泡排序耗时：" << duration1.count() << " ms" << endl;
    cout << "选择排序耗时：" << duration2.count() << " ms" << endl;
    
    return 0;
}

📝 实战练习

📝 理解测试

对于已经有序的数组 [1, 2, 3, 4, 5]，哪种排序算法更快？

选择答案查看解析...

💻 综合挑战

题目：实现一个完整的排序程序：
1. 输入n个整数
2. 分别用冒泡排序和选择排序进行排序
3. 输出排序结果
4. 统计两种排序的比较次数和交换次数
5. 比较两种算法的性能差异

点击"生成代码框架"查看提示...