冒泡排序算法-EW帮帮网

void bubble_sort(int arr[], int sz) // 参数接收数组元素个数 
{
    int i = 0;
    for(i = 0; i < sz - 1; i++) // 外层循环控制排序轮数
    {
        int j = 0;
        for(j = 0; j < sz - i - 1; j++) // 内层循环控制每轮比较次数
        {
            if(arr[j] > arr[j + 1]) // 如果前一个元素大于后一个元素
            {
                // 交换两个元素的位置
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

int main()
{
    int arr[] = {3, 1, 7, 5, 8, 9, 0, 2, 4, 6};
    int sz = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
    bubble_sort(arr, sz); // 调用排序函数
    
    // 打印排序后的数组
    int i = 0;
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

实现思路

1. 算法核心思想

冒泡排序的基本思想是通过反复比较相邻元素，将较大的元素逐步"冒泡"到数组的末端。每一轮排序都会确定一个最大元素的最终位置。

2. 函数参数说明

void bubble_sort(int arr[], int sz)

arr[]: 待排序的整型数组
sz: 数组的长度（元素个数）

3. 外层循环控制排序轮数

for(i = 0; i < sz - 1; i++)

需要进行sz-1轮排序
每完成一轮，最大的元素就会"冒泡"到数组末尾
例如：10个元素的数组需要9轮排序（因为第9轮排序后，剩下的1个元素自然就是最小的）

4. 内层循环控制每轮比较

for(j = 0; j < sz - i - 1; j++)

sz - i - 1表示每轮需要比较的次数
随着轮数i增加，需要比较的元素逐渐减少（因为每轮都会确定一个最大元素的位置）
例如：
- 第1轮(i=0)：比较0到8号元素（共9次比较）
- 第2轮(i=1)：比较0到7号元素（共8次比较）
- ...
- 第9轮(i=8)：比较0号与1号元素（共1次比较）

5. 元素比较与交换

if(arr[j] > arr[j + 1]) {
    int tmp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = tmp;
}

比较相邻的两个元素arr[j]和arr[j+1]
如果前一个元素大于后一个元素，就交换它们的位置
使用临时变量tmp完成交换操作

6. 主函数中的调用过程

int main() {
    int arr[] = {3,1,7,5,8,9,0,2,4,6};
    int sz = sizeof(arr)/sizeof(arr[0]); // 计算数组长度
    bubble_sort(arr, sz); // 调用排序函数
    
    // 打印排序结果
    for(int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

sizeof(arr)/sizeof(arr[0])：计算数组长度的常用方法
排序完成后，通过循环打印排序结果

7. 排序过程示例（以第一轮为例）

初始数组：[3,1,7,5,8,9,0,2,4,6]

第一轮比较过程：

比较3和1 → 交换 → [1,3,7,5,8,9,0,2,4,6]
比较3和7 → 不交换
比较7和5 → 交换 → [1,3,5,7,8,9,0,2,4,6]
比较7和8 → 不交换
比较8和9 → 不交换
比较9和0 → 交换 → [1,3,5,7,8,0,9,2,4,6]
比较9和2 → 交换 → [1,3,5,7,8,0,2,9,4,6]
比较9和4 → 交换 → [1,3,5,7,8,0,2,4,9,6]
比较9和6 → 交换 → [1,3,5,7,8,0,2,4,6,9]

第一轮结束后，最大的元素9已经到达最终位置。

8. 算法特点

时间复杂度：O(n²)（最坏和平均情况）
空间复杂度：O(1)（原地排序）
稳定性：稳定排序（相等元素不会交换位置）
优化空间：可以添加标志位判断是否已经有序，提前结束排序

通过这样逐步的"冒泡"过程，最终可以得到一个完全有序的数组。

三、优化实现（方法2）

基础实现即使在数组已经有序的情况下仍会继续进行比较，效率较低。我们可以通过添加一个标志位来优化：

void bubble_sort(int arr[], int sz) // 参数接收数组元素个数 
{
    int i = 0;
    for(i = 0; i < sz - 1; i++)
    {
        int flag = 1; // 假设这一趟已经有序了
        int j = 0;
        for(j = 0; j < sz - i - 1; j++)
        {
            if(arr[j] > arr[j + 1]) // 如果发生交换
            {
                flag = 0; // 标记为无序
                // 交换元素
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
        if(flag == 1) // 如果这一趟没有发生交换，说明已经有序
            break; // 提前结束排序
    }
}

int main()
{
    int arr[] = {3, 1, 7, 5, 8, 9, 0, 2, 4, 6};
    int sz = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, sz);
    
    // 打印排序结果
    int i = 0;
    for(i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

冒泡排序优化版本与原版的实现区别

1. 核心区别：提前终止机制

优化版本新增了flag标志位，用于检测在一轮比较中是否发生了元素交换，这是两个版本最本质的区别。

2. 具体差异分析

(1) 标志位引入

int flag = 1; // 假设这一趟已经有序了

在每轮比较开始前，先将flag设为1（假设数组已经有序）
原版没有这个标志位，会强制完成所有轮次的比较，这样比较次数会很多

(2) 交换时的标志更新

if(arr[j] > arr[j + 1]) {
    flag = 0; // 标记为无序
    // 交换代码...
}

只要发生一次交换，就将flag设为0（表示数组仍无序）
原版只进行交换操作，不记录交换状态

(3) 提前终止条件

if(flag == 1) // 如果这一趟没有发生交换
    break; // 提前结束排序

当一轮比较结束后检查flag
如果仍为1，说明这轮没有发生任何交换，数组已经有序
原版会继续执行所有剩余的轮次，即使数组已经有序

3. 性能对比

特性	原版冒泡排序	优化版冒泡排序
最好情况(已排序)	O(n²)	O(n)
最坏情况(完全逆序)	O(n²)	O(n²)
平均情况	O(n²)	O(n²)
额外空间	O(1)	O(1)
提前终止能力	无	有

4. 实际运行示例

测试数组：[1, 2, 3, 4, 5]（已经有序）

原版执行过程：

仍然会进行n-1轮比较（4轮）
每轮都会进行完整的内部比较
共需要(n-1)*n/2 = 10次比较

优化版执行过程：

第一轮：
- 比较1-2、2-3、3-4、4-5（无交换）
- flag保持为1
- 检测到flag==1，立即break退出

仅需n-1=4次比较

5. 代码差异图示

// 原版
void bubble_sort(int arr[], int sz) {
    for(int i = 0; i < sz-1; i++) {          // 固定执行n-1轮
        for(int j = 0; j < sz-i-1; j++) {    // 完整比较
            if(arr[j] > arr[j+1]) {           // 仅交换
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

// 优化版
void bubble_sort(int arr[], int sz) {
    for(int i = 0; i < sz-1; i++) {
        int flag = 1;                         // 新增标志位
        for(int j = 0; j < sz-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                flag = 0;                     // 发生交换时标记
                swap(arr[j], arr[j+1]);
            }
        }
        if(flag) break;                      // 提前终止检查
    }
}

6. 适用场景建议

使用原版：
- 教学演示基本算法原理
- 确定数据量极小且不需要优化
- 测试最坏情况性能
使用优化版：
- 实际工程应用
- 数据可能部分有序的情况
- 对性能有基本要求的场景

7. 进一步优化思路

可以在优化版基础上再做改进：

void bubble_sort(int arr[], int sz) {
    int lastSwapPos = sz - 1;  // 记录最后交换位置
    for(int i = 0; i < sz-1; i++) {
        int flag = 1;
        int currentSwapPos = 0; // 当前轮最后交换位置
        for(int j = 0; j < lastSwapPos; j++) {
            if(arr[j] > arr[j+1]) {
                flag = 0;
                swap(arr[j], arr[j+1]);
                currentSwapPos = j;
            }
        }
        lastSwapPos = currentSwapPos;
        if(flag) break;
    }
}

这种改进可以进一步减少不必要的比较次数。

四、算法分析

时间复杂度：
- 最坏情况（逆序数组）：O(n²)
- 最好情况（已排序数组，使用优化版本）：O(n)
- 平均情况：O(n²)
空间复杂度：O(1)，属于原地排序算法
稳定性：冒泡排序是稳定的排序算法，因为相等的元素不会交换位置
适用场景：
- 小规模数据排序
- 对稳定性有要求的场景
- 作为教学示例理解排序算法基本原理

优化后的冒泡排序在最好情况下（数组已经有序）只需进行一轮比较即可结束，大大提高了效率。

冒泡排序算法

一、基本思想

二、基础实现（方法1）