公告
欢迎来到我的博客喵。
436 字
2 分钟
冒泡排序
冒泡排序的定义
冒泡排序（Bubble Sort）：重复地遍历待排序的数组，比较相邻的元素，如果它们的逆序就交换它们。这个过程持续进行，直到没有需要交换的元素为止，数组即被排序。
每一次遍历都会将当前未排序部分的最大元素“冒泡”到该部分的末尾。相当于元素归位，不再移动。
算法步骤
-
从数组的第一个元素开始，依次比较相邻的两个元素。
-
如果前一个元素大于后一个元素，则交换它们的位置。
-
对每一对相邻元素重复上述步骤，直到数组的末尾。此时，当前未排序部分的最大元素已经被移动到末尾。
-
重复上述过程，对剩余的未排序部分进行排序，直到整个数组有序。
代码实现
array<int, 5> bubbleSort(array<int, 5> arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { // 每次遍历将未排序部分的最大元素冒泡到末尾 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); // 交换 } } } return arr;}时间复杂度分析
主要是看比较和交换操作：
-
最好情况：当数组已经有序时，每次比较都不需要交换，时间复杂度为 O(n)。
-
最坏情况：当数组是逆序时，每次比较都需要交换，时间复杂度为 O(n^2)。
-
平均情况：无论数组初始状态如何，平均时间复杂度仍为 O(n^2)。
稳定性
冒泡排序是稳定的排序算法，因为相等元素的相对顺序不会改变。