冒泡排序 - 简书

冒泡排序

废话不多说先上代码

void bubbleSort(int arr[], int length) {
    int temp;
    int flag = 1;
    
    for(int i = 1; i < length; ++i) {
        if(flag == 0)
            break;
        flag = 0;
        for(int x = 0; x < length - i; ++x) {
            if(arr[x] > arr[x + 1]) {
                temp = arr[x];
                arr[x] = arr[x + 1];
                arr[x + 1] = temp;
                flag = 1;
            }
        }
    }

    return;
}

时间复杂度

O(n²)

空间复杂度

O(1) 原地排序

稳定排序

是稳定排序

算法核心思想

假设要排序的数组的下标为0 到 5。下面所有的数字都代表其下标在数组中对应的数。
比较 0 和 1，如果 0 大于 1 就交换他们的位置，然后对比 1 和 2，如果 1 大于 2 就交换他们的位置，以此类推。
一轮要比较多少次呢？答案是数组长度减1次，这个比较次数可以随着轮次的增加而减少，因为每一轮比较和交换过后，最后的数一定是最大的数。
一共要进行多少轮呢？答案是数组长度减1次。这个次数是固定的，但是我们可以加入flag标记，如果数组已经有序了就跳出循环。

一步一步实现冒泡排序

内层循环，实现对比交换每个数字。

void bubbleSort(int arr[], int length) {
    int temp;
//我每次拿 i 和 i + 1 进行比较，当 i 等于 length 的时候 i + 1 就已经越界了（超出长度限制，所以我们循环只到 length - 1）
    for(int i = 0; i < length - 1; ++i) {
        //如果前面的数大于后面的数 就交换位置
        if(arr[i] > arr[i + 1]) {
            temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}
//一轮循环结束后，最大的已经在最后了

外层循环
因为内层循环一轮只能把一个最大的数放在最后，所以我们还有进行多次内层循环。

void bubbleSort(int arr[], int length) {
    int temp;
    //每次能将一个移动到最后，那么一共需要进行 length - 1 次循环
    for(int x = 0; x < length - 1; ++x) {
        //我每次拿 i 和 i + 1 进行比较，当 i 等于 length 的时候 i + 1 就已经越界了（超出长度限制，所以我们循环只到 length - 1）
        for(int i = 0; i < length - 1; ++i) {
            //如果前面的数大于后面的数 就交换位置
            if(arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
}
//到此 简单的冒泡排序就已经结束了

细节优化
这里我们可以优化一些细节。
内层循环次数，外层循环次数

void bubbleSort(int arr[], int length) {
    //使用flag 减少外层循环次数 如果数组经过几轮交换后就已经有序了，这时我们可以跳出循环;
    int flag = 1;
    int temp;
    //每次能将一个移动到最后，那么一共需要进行 length - 1 次循环
    for(int x = 1; x < length; ++x) {
        //flag 等于 0 说明上轮循环没有交换任何数据，数组已经有序了。
        if(flag == 0)
            break;
        flag = 0;
        //我每次拿 i 和 i + 1 进行比较，当 i 等于 length 的时候 i + 1 就已经越界了（超出长度限制，所以我们循环只到 length - 1）
        //因为每一轮循环都将最大的数放到了最后，就没必要和最后的数进行比较了
        //内存循环的次数为 length - 1、length - 2、length - 3 ……，这时我们可以借助外层循环的参数实现。
        for(int i = 0; i < length - x; ++i) {
            //如果前面的数大于后面的数 就交换位置
            if(arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = 1;
            }
        }
    }
}
// OK 优化也已经完成了

到此冒泡排序已经结束了，你学会了吗？

冒泡排序还是很简单的，优化这里只是稍稍有点绕而已，加油~
记得点赞哦。