tags:
  - DSA

SA. Bubble Sort

排序算法的作用是将一组元素按照指定顺序进行排列。常见的顺序包括数字从小到大的升序排列、字母从 A 到 Z 的字典序排列，也可以是其他任意顺序（如降序排列）。高效的排序算法对于系统至关重要，因为它在一定程度上会影响系统的整体性能，尤其是在需要频繁处理大规模数据时。

Bubble Sort (Since 1956)

冒泡排序可以说是最简单的排序算法，它的核心思想是通过多次一步一步地比较和交换（遍历数组），将较大的元素逐步“冒泡”到序列的末尾。每次交换前，都需要需要比较相邻的元素，如果顺序错误，就将两个数据元素进行一次交换（称为”冒泡“）。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

我们来分析一下冒泡排序的时间/空间复杂度。

最坏情况：
数组完全逆序，那么我们就需要遍历所有未排序的元素。也就是遍历 n-1 次，每次遍历比较 n-i-1 次。如此，总共的比较和交换的次数就是：即我们的最坏时间复杂度为 )。
最好情况：
数组完全有序，这时我们在第一遍遍历时并不会有任何的交换操作，标志位为 false 直接终止。如此我们只需要比较次（次交换）。最好的时间复杂度为。
空间复杂度：
空间复杂度呢？因为冒泡排序只需要使用一个元素空间 temp ，所以它的空间复杂度为。