冒泡排序

1. 冒泡排序算法
2. 冒泡排序算法示例
3. 冒泡排序算法的实现
4. 冒泡排序算法的复杂度

冒泡排序是一种简单的排序算法。它的工作原理是对相邻元素进行反复比较，如果它们的顺序不对，则进行交换。反复比较后，将最小/最大的元素向数组最后冒泡，因此这种算法被命名为冒泡排序。虽然效率不高，但它仍然代表了排序算法的基础。

冒泡排序算法

假设我们有一个未排序的数组 A[]，包含 n 个元素。

上述算法中的第 1 步也称为执行。要对一个大小为 n 的数组进行排序，需要进行 n-1 次的执行。

冒泡排序算法示例

假设我们有数组：(5,3,4,2,1). 我们将使用冒泡排序算法对其进行排序。

• 第一次执行：

• 第二次执行：

• 第三次执行：

• 第四次执行：

第四次执行后，我们得到排序数组 - (1 2 3 4 5)。

冒泡排序算法的实现

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubble_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

冒泡排序算法的复杂度

时间复杂度

• 平均情况

平均来说，在冒泡排序的第 i 次执行中，会进行 n-i 次比较。因此，如果有 n 个通道，那么平均的时间复杂度可以用以下方式给出

(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2

因此，时间复杂度为 O(n²)。

• 最坏情况

最坏的情况发生在数组被反向排序的时候，并且必须执行最大数量的比较和交换。

最坏的情况下时间复杂度是 O(n²)。

• 最佳情况

最好的情况发生在数组已经被排序的时候，那么只需要进行 N 次比较。

最佳情况下的时间复杂度为 O(n)。

空间复杂度

这个算法的空间复杂度是 O(n)，因为除了一个临时变量外，不需要额外的内存。