文章目录
1. 冒泡排序
1.1 简介
冒泡排序（Bubble Sort）是一种简单的排序算法，其基本思想是通过相邻元素的比较和交换，把最大的元素逐步“冒泡”到列表的末尾。该算法的名称来源于较小的元素会逐渐“浮”到列表的顶端，而较大的元素则逐渐“沉”到列表的底部，就像气泡在水中上升和下沉一样。
1.2 基本步骤：
-
比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大，则交换它们的位置。
-
遍历列表：重复上述过程，直到列表的末尾。这一轮操作结束后，最大的元素会被移动到列表的最后一个位置。
-
重复步骤：再次从列表的第一个元素开始，重复上述过程，但这次不再包括最后一个已经排好的元素。
-
终止条件：重复上述步骤，直到整个列表有序（即没有需要交换的元素）。
1.3 示例代码（C）
#include <stdio.h>
// 冒泡排序函数
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++) {
// 提前退出标志，如果在一轮中没有发生交换，说明数组已经有序
int swapped = 0;
for (j = 0; j < n-i-1; j++) {
// 如果前一个元素大于后一个元素，则交换它们
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1; // 标记发生了交换
}
}
// 如果没有发生交换，说明数组已经有序，提前退出循环
if (swapped == 0) {
break;
}
}
}
// 打印数组函数
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 主函数
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("排序前的数组: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
1.4 复杂度分析
-
时间复杂度：
- 最优情况（列表已经有序）：O(n)，因为只需遍历一次就可以确定列表已经有序。
- 最坏情况（列表完全逆序）：O(n^2)，因为每一轮都需要遍历整个列表，并且需要进行n-1次比较和交换。
- 平均情况：O(n^2)
-
空间复杂度：O(1)，因为冒泡排序是原地排序，不需要额外的存储空间。
1.5 动画展示
