冒泡排序：简单易懂的排序算法解析

创作时间:

作者:

@小白创作中心

冒泡排序：简单易懂的排序算法解析

引用

CSDN

https://blog.csdn.net/2302_78391795/article/details/139692652

冒泡排序是一种简单直观的排序算法，通过重复遍历待排序序列，比较相邻元素并必要时交换位置，最终实现序列的有序化。本文将从基本原理、实现方法、优化策略到应用场景等多个维度，全面解析这一基础排序算法。

一、引言

排序算法是计算机程序设计中的一种重要操作，其功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

二、冒泡排序原理

基本思想：

通过重复地遍历待排序的序列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。

算法过程：

比较相邻元素：重复地走访需要排序的元素列表，依次比较两个相邻的元素。
交换元素：如果顺序（如从大到小或从小到大）错误，就交换这两个元素的位置。
重复进行：重复以上步骤，直到没有相邻的元素需要交换，则元素列表排序完成。

三、冒泡排序的实现

对于循环趟数和比较次数的控制，如图所示。以升序排序为例，每一趟排序可以将一个较大的值放在后面。

循环趟数：
若数组大小为size，则最多需要进行size-1趟排序
（当排序size-1次之后，后面的size-1个元素已经被放在了正确的位置，剩下的一个元素自然不需要排序了）

比较次数：
若数组大小为size，则每一趟需要比较的次数是不同的
第一趟每两个元素都需要比较一次，总共是size-1次
第二趟排序，最后一个元素不需要比较，所以需要比较size-2次
……
总结成规律，每一趟需要比较的次数为size-1-（趟数-1）次

//冒泡排序
void BubbleSort1(DataType* a, int size)//升序排序
{
    for (int i = 0; i < size - 1; i++)//控制排序趟数
    {
        for (int j = 0; j < size - 1 - i; j++)//控制每次比较次数
        {
            if (a[j] > a[j + 1])//不满足升序就交换位置
            {
                DataType tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}
void BubbleSort2(DataType* a, int size)//降序排序
{
    for (int i = 0; i < size - 1; i++)//控制排序趟数
    {
        for (int j = 0; j < size - 1 - i; j++)//控制每次比较次数
        {
            if (a[j] < a[j + 1])//不满足降序就交换位置
            {
                DataType tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

四、冒泡排序的优化

优化方法
设置一个标志位来判断是否发生了交换，从而提前结束排序

void BubbleSort(DataType* a, int size)//升序排序
{
    for (int i = 0; i < size - 1; i++)//控制排序趟数
    {
        int flag = 1;//标志位
        for (int j = 0; j < size - 1 - i; j++)//控制每次比较次数
        {
            if (a[j] > a[j + 1])//不满足升序就交换位置
            {
                flag = 0;//如果发生交换，改变标志位
                DataType tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
        if (flag == 1)//如果一趟排序没有发生交换，说明数据已经有序，可以提前结束
            break;
    }
}