当前位置： 首页 > article >正文

冒泡排序的缺陷及优化

article 2025/2/19 18:31:24

冒泡排序的缺陷及优化

定义： 

冒泡排序（Bubble Sort）是一种简单且常用的排序算法。其基本思想是通过多次遍历待排序的序列，依次比较相邻的两个元素，并根据需要交换它们的位置，使得较大的元素逐渐向后移动，较小的元素逐渐向前移动。这个过程类似于水中的气泡逐渐上升，因此得名“冒泡排序”。

操作步骤

  1. 比较第 1 个和第 2 个元素，按大小排序。

  2. 移动到下 1 个对（第 2 和第 3），继续比较和排序。

  3. 重复这个过程，每轮结束后将最大（小）的数“沉”到数组末尾。

实现 

基本实现：冒泡排序

分析

排序过程如下图所示：

17a4a34de62dfd59cc6cddf2b62dedd2.jpeg

  • 设定数组长度为n。

  • 外层循环用于控制总的遍历次数，最多需要 n-1 次。

  • 内存循环用于比较并排序相邻元素。

  • 每经过一轮遍历，总会把当前遍历最后一个数放在最末未，所以内循环次数随着外循环次数增加而减少。具体关系为：当前内循环次数 = n - 1 - 当前外循环次数 。

代码

使用冒泡排序方法，从大到小排序数据。编写代码如下

/**
 * @ 基本实现：冒泡排序
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */ 
void bubble_sort(int *arr, int num)
{
    int i, j, tmp;

    for (i=0; i<num-1; i++) {
        for (j=0; j<num-i-1; j++) {
            if (arr[j] < arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

}

运行结果
1094395ff0db399c06687e20cfc5bd02.png

优化 1. 短路法

分析
0221352b94a27bfd8f2e178f6b032414.png

  • 由上图可以看出，在第 1 轮遍历完成，就已经得到我们需要的排序顺序，此时第 2 、3、4 轮遍历数据完全无交换过程（浪费时间）。

  • 当某一轮遍历数据完全无交换即可表示此时我们的排序已完成，可以完全跳过后序遍历。从而提高排序效率。

  • 此功能在数据本身是有序的情况下将会大大减少排序过程。

代码

在冒泡的基础上，加入短路判断，若当前排序已完成，提前退出排序。编写代码如下

/**
 * @ 优化 1：冒泡排序，短路优化，如果某一轮没有发生交换，说明数组已经排序完成，提前退出。
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */ 
void bubble_sort_short_circuit(int *arr, int num)
{
    int i, j, tmp;
    char change_flag = 0;   /* 交换标志，1表示当前有交换 */

    for (i=0; i<num-1; i++) {
        change_flag = 0;
        for (j=0; j<num-i-1; j++) {
            if (arr[j] < arr[j+1]) {    /* 数据不符合从大到小规则，交换 */
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                change_flag = 1;
            }
        }

        /* 若是某一轮没有发生交换，说明数组已经排序完成，提前退出 */
        if (!change_flag) {
            printf("quit i[%d] j[%d]\n", i, j);
            break;
        }
    }
}
运行结果
a5249e223bb5f5b697a1efb4b35a22e9.png

优化 2.鸡尾酒排序

分析
a5ce3bc5f910d44f05e5ff0a8a076bd5.jpeg

  • 为进一步提高效率，采用双向扫描的方式。

  • 设定左右指针 left 和 right。

  • 在每 1 轮中进行 2 次扫描——从左到右将较大的元素移到右边，再从右到左将较小的元素移到左边。

  • 如果某次循环没有发生任何交换，说明数组已排序完成。

代码

使用鸡尾酒排序方式。编写代码如下

/**
 * @ 优化 2：鸡尾酒排序，每一轮遍历先从左到右，再从右到左，可以更快减少未排序数据。
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */ 
void cocktail_shaker_sort(int *arr, int num)
{
    int i, tmp;
    char change_flag = 1;           /* 交换标志，1表示当前有交换 */
    int left = 0, right = num-1;    /* 用于控制左右遍历 */

    while ((left <= right) && change_flag) {
        change_flag = 0;
        /* 从左至右，将最小的数移动到最后面 */
        for (i=left; i<right; i++) {
            if (arr[i] < arr[i+1]) { 
                tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
                change_flag = 1;
            }
        }
        left++;

        /* 从右至左，将最大的数移动到最前面 */
        for (i=right-1; i>=left; i--) {
            if (arr[i] > arr[i-1]) { 
                tmp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = tmp;
                change_flag = 1;
            }
        }
        right--;
    }
}
运行结果
8ee2e16b13e29e18a4b9e672c4e87242.png

完整代码 

/**
 * @Filename : bubble_sort.c
 * @Revision : $Revision: 1.00 $
 * @Author : Feng(更多编程相关的知识和源码见微信公众号：不只会拍照的程序猿，欢迎订阅)
 * @Description : 冒泡排序的缺陷及优化
**/

#include <stdio.h>
#include <string.h>

#define MAX_NUM     5  

/**
 * @ 打印数组
 * @ arr - 待打印的数组     num - 数组元素个数
 * */
void print_arr(int *arr, int num) 
{
    int i;

    for (i=0; i<num; i++)
        printf("%02d ", arr[i]);
    printf("\n");
}

/**
 * @ 基本实现：冒泡排序
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */
void bubble_sort(int *arr, int num)
{
    int i, j, tmp;

    printf("排序前数组内容: ");
    print_arr(arr, num);

    for (i=0; i<num-1; i++) {
        for (j=0; j<num-i-1; j++) {
            if (arr[j] < arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
            printf("第%d轮第%d次排序: ", i+1, j+1);
            print_arr(arr, num);
        }
    }

    printf("排序后数组内容: ");
    print_arr(arr, num);
}

/**
 * @ 优化 1：冒泡排序，短路优化，如果某一轮没有发生交换，说明数组已经排序完成，提前退出。
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */
void bubble_sort_short_circuit(int *arr, int num)
{
    int i, j, tmp;
    char change_flag = 0;   /* 交换标志，1表示当前有交换 */

    printf("排序前数组内容: ");
    print_arr(arr, num);

    for (i=0; i<num-1; i++) {
        change_flag = 0;
        for (j=0; j<num-i-1; j++) {
            if (arr[j] < arr[j+1]) {    /* 数据不符合从大到小规则，交换 */
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                change_flag = 1;
            }
            printf("第%d轮第%d次排序: ", i+1, j+1);
            print_arr(arr, num);
        }

        /* 若是某一轮没有发生交换，说明数组已经排序完成，提前退出 */
        if (!change_flag) {
            //printf("quit i[%d] j[%d]\n", i, j);
            break;
        }
    }

    printf("排序后数组内容: ");
    print_arr(arr, num);
}

/**
 * @ 优化 2：鸡尾酒排序，每一轮遍历先从左到右，再从右到左，可以更快减少未排序数据。
 * @ arr - 待排序的数组     num - 数组元素个数
 * @ 要求从大到小排序数据
 * */
void cocktail_shaker_sort(int *arr, int num)
{
    int i, tmp;
    char change_flag = 0;           /* 交换标志，1表示当前有交换 */
    int left = 0, right = num-1;    /* 用于控制左右遍历 */
    int cnt = 0, cntleft, cntright; /* 记录排序次数 */

    printf("排序前数组内容: ");
    print_arr(arr, num);

    while (left <= right) {       
        /* 从左至右，将最小的数移动到最后面 */
        change_flag = 0;
        cntleft = 0;
        cntright = 0;
        for (i=left; i<right; i++) {
            if (arr[i] < arr[i+1]) { 
                tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
                change_flag = 1;
            }
            cntleft++;
            printf("第%d轮第%d次排序(从左至右): ", cnt+1, cntleft);
            print_arr(arr, num);
        }
        if (!change_flag)
            break;
        left++;

        /* 从右至左，将最大的数移动到最前面 */
        change_flag = 0;
        for (i=right-1; i>=left; i--) {
            if (arr[i] > arr[i-1]) { 
                tmp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = tmp;
                change_flag = 1;
            }
            cntright++;
            printf("第%d轮第%d次排序(从右至左): ", cnt+1, cntright);
            print_arr(arr, num);
        }
        
        if (!change_flag)
            break;
            
        right--;
        cnt++;
    }

    printf("排序后数组内容: ");
    print_arr(arr, num);
}

int main(void)
{
    int buf0[] = {3, 8, 5, 1, 2};
    int buf1[] = {3, 8, 5, 1, 2};
    int buf2[] = {3, 8, 5, 1, 2};
    
    printf ("----------冒泡排序---------\n");
    bubble_sort(buf0, MAX_NUM);

    printf ("----------短路优化---------\n");
    bubble_sort_short_circuit(buf1, MAX_NUM);

    printf ("---------鸡尾酒排序---------\n");
    cocktail_shaker_sort(buf2, MAX_NUM);
    
    return0;
}

运行结果 

4435adf8f8003b4ddc8d1a343925c617.png

总结 

复杂度

  • 时间复杂度：最坏情况下为O(n²)，平均情况下也为O(n²)，效率较低。

  • 空间复杂度：O(1)，属于原地排序算法。

优点

  • 实现简单，易于理解和实现。

  • 空间复杂度低，属于原地排序算法。

缺点

  • 时间复杂度较高，不适合大规模数据的处理。

  • 对于最坏情况（数组完全逆序），效率低下。

优化

  • 短路优化：若某一轮遍历中完全没发生交换，可以提前结束。这在最好情况下非常有效。

  • 鸡尾酒排序：双向遍历，可以更快将元素放到正确位置，减少比较次数。

总结

冒泡排序虽然在实际应用中并不常用，但由于其简单性和教学价值，常被用作学习排序算法的基础。对于小规模数据或需要简单排序的情况，它仍是一个不错的选择。通过了解冒泡排序的基本原理和优化版本，我们可以更好地理解更复杂的排序算法的设计思想。


http://www.kler.cn/a/546598.html

相关文章：

  • HtmlRAG：RAG系统中，HTML比纯文本效果更好
  • 面向 Data+AI 的新一代智能数仓平台
  • flutter doctor 报错—CocoaPods not installed
  • Java实现HTTPS双向认证的终极指南：从原理到实战
  • [创业之路-297]：经济周期与股市、行业的关系
  • Git 查看修改记录 二
  • 《安富莱嵌入式周报》第350期：Google开源Pebble智能手表，开源模块化机器人平台，开源万用表，支持10GHz HRTIM的单片机，开源CNC控制器
  • 京东 旋转验证码 分析
  • 网络安全事件分级
  • 通过 VBA 在 Excel 中自动提取拼音首字母
  • 微软AutoGen高级功能——Swarm
  • 大语言模型评价 怎么实现去偏见处理
  • 47 AVL树的实现
  • 网络安全学习记录
  • 实践记录-NAS入手前后的记录-关于设备选型的练习
  • leetcode 2915. 和为目标值的最长子序列的长度
  • AIGC与AICG的区别解析
  • 阿里云IOT消息处理
  • AWS上基于高德API验证Amazon Redshift里国内地址数据正确性的设计方案
  • wx060基于springboot+vue+uniapp的宿舍报修系统小程序