当前位置：首页 > news >正文

温岭市住房和城乡建设规划局网站东莞市网络优化推广服务机构

news 2025/11/7 22:36:00

温岭市住房和城乡建设规划局网站,东莞市网络优化推广服务机构,云虚拟主机怎么做2个网站,织梦做的网站网速打开慢是怎么回事一、什么是冒泡排序？ 冒泡排序（Bubble Sort）是一种经典的排序算法，其工作原理非常直观：通过多次比较和交换相邻元素，将较大的元素“冒泡”到数组的末尾。经过多轮迭代，整个数组会变得有序。二…

一、什么是冒泡排序？

冒泡排序（Bubble Sort）是一种经典的排序算法，其工作原理非常直观：通过多次比较和交换相邻元素，将较大的元素“冒泡”到数组的末尾。经过多轮迭代，整个数组会变得有序。

二、冒泡排序的核心思想

比较相邻元素：
- 从数组的起始位置开始，逐个比较相邻的两个元素。
- 如果顺序不符合（如升序时前一个元素大于后一个元素），则交换两者的位置。
逐步缩小范围：
- 每一轮结束后，当前未排序部分中最大的元素会移动到正确的位置。
- 下一轮只需处理前面的未排序部分。

三、冒泡排序的实现步骤

从数组的第一个元素开始，与相邻元素进行比较。
如果顺序不对，交换这两个元素。
每轮操作后，将最大的元素固定在数组的最后。
重复上述步骤，直到数组完全有序。

四、冒泡排序的 C 语言实现

基本实现

以下是冒泡排序的基本实现代码：

#include <stdio.h>// 冒泡排序函数
void bubbleSort(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]) { // 比较相邻元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 主函数
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");bubbleSort(arr, n);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

五、输入输出示例

输入

数组：[64, 34, 25, 12, 22, 11, 90]

输出

排序前的数组：64 34 25 12 22 11 90
排序后的数组：11 12 22 25 34 64 90

六、复杂度分析

时间复杂度：
- 最坏情况（完全逆序）：( O(n^2) )
- 最好情况（已排序）：( O(n^2) )（未优化情况下）。
空间复杂度：
- 只使用了常量空间，空间复杂度为 ( O(1) )。
稳定性：
- 冒泡排序是稳定的，因为它不会改变相等元素的相对顺序。

七、优化冒泡排序

1. 提前终止的优化

在某一轮比较中，如果没有发生交换，说明数组已经有序，可以提前结束排序。

void optimizedBubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int swapped = 0; // 标记变量for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1; // 标记发生了交换}}if (!swapped) break; // 如果没有发生交换，提前结束}
}

2. 双向冒泡排序（鸡尾酒排序）

普通冒泡排序每轮只向一个方向“冒泡”，双向冒泡则在一轮中从两端同时冒泡，缩小范围。

void cocktailSort(int arr[], int n) {int swapped = 1;int start = 0, end = n - 1;while (swapped) {swapped = 0;// 从左向右冒泡for (int i = start; i < end; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}if (!swapped) break;swapped = 0;end--;// 从右向左冒泡for (int i = end - 1; i >= start; i--) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}start++;}
}