冒泡排序详解

冒泡排序乃是一种基础性的交换排序算法，其核心要义在于反复对数组进行遍历，将相邻元素加以比较，一旦顺序有误即予以交换。每一轮的遍历皆会使未排序部分的最大值“浮升”至恰当位置，且遍历的次数渐次递减。

算法步骤

1. 外层循环：其用于掌控遍历的轮数（总计 n - 1 轮）。
2. 内层循环：对相邻元素予以比较，若 arr[j] > arr[j + 1] ，则进行交换。
3. 提前终止优化：倘若某一轮未发生交换，这表明数组已然有序，可直接结束。

C++ 示例代码

#include 
using namespace std;

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - i - 1 j if arrj> arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 无交换则已有序，提前退出
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

时间复杂度分析

空间复杂度

• 原地排序：仅需常数级的额外空间，其复杂度为 O(1)。

稳定性

• 稳定排序：相等元素的相对位置保持不变。

适用场景

1. 小规模数据：适用于数据量相对较小的情形