​【数据结构与算法】冒泡排序：简单易懂的排序算法解析

一、引言

排序算法的简介

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

二、冒泡排序原理

🍃基本思想：

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

🍃算法过程：

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

三、冒泡排序的实现

对于循环趟数和比较次数的控制，如图所示

以升序排序为例，每一趟排序可以将一个较大的值放在后面

循环趟数：

若数组大小为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;
  }
}

五、冒泡排序的优缺点

1. 优点：简单易懂，容易实现，稳定性好（相等的元素在排序后不会改变相对顺序）。
2. 缺点：效率较低，尤其是当待排序序列已经有序或接近有序时，仍然需要执行完整的排序过程。

六、冒泡排序的应用场景

1. 小型数据集：对于小型数据集，冒泡排序的简洁性和稳定性使其成为一个不错的选择。
2. 教学示例：由于冒泡排序的直观性和易于理解性，它经常被用作教学示例来介绍排序算法的基本概念和原理。

总结

• 冒泡排序，作为一种简单的排序算法，其核心思想是通过不断交换相邻两个元素的位置，使得每一轮迭代后，当前未排序部分的最大值（或最小值，取决于排序的方向）能够“冒”到序列的一端。尽管其时间复杂度在大数据集上并不理想，但冒泡排序在理解算法的基本思想和调试教学等方面仍具有不可忽视的价值。
• 通过冒泡排序的学习，我们可以深入理解排序算法的基本步骤和原理，为后续学习更高效的排序算法（如快速排序、归并排序等）打下坚实的基础。同时，冒泡排序的直观性也使得它成为算法教学的常用工具，有助于初学者建立对算法设计和实现的直观认识。
• 在实际应用中，我们通常会选择时间复杂度和空间复杂度更优的排序算法来处理大规模数据。但冒泡排序的简洁性和易理解性，使其在特定场合（如小规模数据排序、算法教学等）仍具有实用价值。
• 冒泡排序作为一种经典的排序算法，不仅具有其独特的学术价值，也为后续学习更复杂的算法提供了有益的参考和启示。通过掌握冒泡排序的思想和实现方法，我们可以更好地理解排序算法的本质，为后续的学习和研究打下坚实的基础。