【八大经典排序算法】冒泡排序

一、概述

冒泡排序由于其简单和易于理解，使其成为初学者学习排序算法的首选，也是初学者接触到的第一个排序算法。其原理是通过重复交换相邻的元素来将最大的元素逐步“冒泡”到最后。冒泡排序由美国计算机科学家冯·诺伊曼（John von Neumann）于1945年提出。

冯·诺伊曼是计算机科学和现代计算机体系结构的奠基人之一，他在设计计算机算法时，意识到排序是计算机科学中的一个基本问题。于是，他提出了冒泡排序算法。

冒泡排序的思想是基于比较相邻元素的大小，如果顺序不正确，则交换它们的位置。通过多次遍历数组，每次都将最大的元素“冒泡”到末尾，最终实现整个数组的排序。

二、思路解读

我们知道冒泡排序的基本思想本思想是通过不断交换相邻元素的位置，将最大（或最小）的元素逐步“冒泡”到序列的末尾。（接下来以升序为例）

我们可以从序列的第一个元素开始，依次比较相邻的两个元素的大小。如果前一个元素大于后一个元素，则交换它们的位置，相当于将较大的元素冒泡到后面。然后继续对剩余的元素进行比较和交换，直到最后一个元素，此时最大的元素就成功冒泡到序列的末尾啦。

上述过程我们已经将整个排序中最大的数冒泡到了最尾端，接下啦要做的就是不断重复上述步骤，每次需比较和交换的范围缩小一个元素，直到整个序列有序为止。

动画演示：

三、代码实现

上述思路如何转换为代码呢？（以升序为例）

我们可以通过双重循环来实现。

第一层循环表示要排序的次数。假设我们有n个元素，此时我们只需要排序n-1次，让最后n-1个元素有序，此时剩余的最后一个元素一定是最小的。

第二层排序表示将每次排序中的最大数冒泡到最后。需要注意的是，我们每完成一次排序，待排序的元素个数就少1。

【代码】：

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void BubbleSort(int* a, int n)
{
  //排序n-1次
  for (int i = 0; i < n - 1; i++)
  {
    //将最大元素冒泡到最后
    //为什么边界条件是n-1-i呢？
    //因为n个数，两两比较，即比较n-1对。同时每排序完i次，待排序的个数就减i。
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
      }
    }
  }
}

四、优化

上述代码已经可以完整实现一个排序了。但有一个问题，如果我们带排序的数据接近有序呢？比如：

我们发现只需要简单交换1次即可。但按原来代码所示，一次过后虽然排序已经有序了，但还是要继续比较的。未免太死板了。

所以我们可以在每次排序前多加一个变量flag，每次排序过程中如果有数据交换，就改变flag的值。

最后，我们只需通过判断flag的值是否改变即可判断是否已经有序。如果flag的值没改变（以升序为例），则说明数据中后一项都比前一项大，此时数组有序。

【最终代码】：

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int flag = 1;
    for (int j = 0; j < n - 1 - i; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
        flag = 0;
      }
    }
    if (flag)
      break;
  }
}

时间复杂度：O(N^2)

空间复杂度：O(1)