气泡排序¶

1 定义¶

冒泡排序是一种算法，用于比较相邻元素，并在相邻元素未按预期顺序进行交换时交换它们的位置。顺序可以是升序或降序。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2 气泡排序工作步骤¶

从第一个索引开始，比较元素 1 和 2，位置不对则进行交换，直到最后一个元素。这样保证最后一个元素是最大元素，我们称为已排序元素

第 1 次排序

跟之前一样，直到最后一个未排序元素。

第 2,3,4 次排序

3 程序¶

void bubbleSort(int array[], int size)
{
  for (int step = 0; step < size - 1; ++step)
  {
    for (int i = 0; i < size - step - 1; ++i)
    {
      if (array[i] > array[i + 1])// 升序，降序反过来
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

int main()
{
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
}

4 算法优化¶

上边工作步骤可以感觉到，如果顺序已经排好，还要进行所有比较。
我们设置信号量==swap==，如果本次没有发生排序，则直接结束。

5 优化程序¶

void bubbleSort(int array[], int size)
{
for (int step = 0; step < size - 1; ++step)
  {
    int swapped = 0;
    for (int i = 0; i < size - step - 1; ++i)
    {
      if (array[i] > array[i + 1])
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped++;
      }
    }
    if (swapped == 0)
      break;
  }
}

int main()
{
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
}

6 复杂度¶

迭代	比较次数
第 1 次迭代	n-1
第 2 次迭代	n-2
第 3 次迭代	n-3
...	...
第 n 次迭代	1

总次数 = (n-1) + (n-2) + (n-3) +.....+ 1 = n (n-1)/2 近似 n²

7 应用¶

数据已经是快排好的