Initial commit

1 files changed, 109 insertions, 0 deletions

diff --git a/content/posts/【数据结构与算法】冒泡排序.md b/content/posts/【数据结构与算法】冒泡排序.md
new file mode 100644
index 0000000..f0f08d9
--- /dev/null
+++ b/content/posts/【数据结构与算法】冒泡排序.md
@@ -0,0 +1,109 @@
+---
+abbrlink: 403994443
+categories:
+- 往昔
+date: "2025-05-10 20:06:05"
+tags:
+- 数据结构与算法
+title: 【数据结构与算法】冒泡排序
+---
+
+## 核心思想
+
+通过相邻元素的两两比较，将较大的元素逐步“冒泡”到数组末尾，每轮排序确定一个最大元素的最终位置。
+
+## 代码实现
+
+```c
+void bubble_sort(int arr[], int n) {
+  // 最外层控制循环轮数 n-1轮
+  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;
+      }
+    }
+  }
+}
+
+// 调用
+void print_array(int arr[], int size) {
+  for (int i = 0; i < size; i++) {
+    printf("%d,", arr[i]);
+  }
+  printf("\n");
+}
+
+int main() {
+  int arr[] = {23, 232, 55, 2, 7, 0, 576, 342};
+  int n = sizeof(arr) / sizeof(arr[0]);
+
+  printf("排序前：");
+  print_array(arr, n);
+  bubble_sort(arr, n);
+
+  printf("排序后");
+  print_array(arr, n);
+}
+```
+
+
+
+## 原理分析
+
+### 外层循环的 i < n - 1 
+
+- n个元素的数组最多需要n-1轮冒泡，如5元素数组需要4轮排序
+- **数学依据**：每轮将一个最大值“沉底”，当完成n-1轮时，最后一个元素必然有序
+
+示例验证：
+
+```
+原始数组：[3, 1, 4, 2]
+第一轮：[1, 3, 2, 4] （确定最大值4）
+第二轮：[1, 2, 3, 4]
+```
+
+用文字解释上面的函数，原理就是在循环中对比数组第i个元素和i+1（即后一位）元素的大小，若i > i +1 则把两者交换位置，随着循环的进行，数组就会被排序。
+
+### 内层循环的 j < n - i - 1
+
+- 动态缩小范围：每轮结束后末尾i个元素已有序
+- 比较次数：第i轮需要比较(n-1)-i次相邻元素
+
+想象一下数组的线性结构，实际上就是在计算排序后的一位的前一位，这样就不会处理已经排序好的元素，进入下一轮循环时可正常排序。
+
+### 数组长度n的计算机制
+
+在main函数中，对于n的计算，采用了`sizeof(arr) / sizeof(arr[0])`的方式。可以这么理解。
+
+```c
+int arr[] = {6,4,8,2};
+假设int占用4字节，计算整个数组的内存占用
+sizeof(arr) = 5 * 4 = 20
+sizeof(arr[0]) = 4
+n = 20 / 4 = 5
+```
+
+计算出数组的总占用，再除以单个占用，就可以得到元素个数了。
+
+### 参数n的作用
+
+- 循环控制：确定外层循环次数n-1次
+- 边界保护，防止越界
+- 效率优化：避免无效比较，如j<n-i-1
+
+## 最坏情况
+
+冒泡排序的最坏情况发生在**输入数组完全逆序情况下**，此时算法需要进行最大次数的比较和交换操作，时间复杂度达到最高。
+
+当待排序数组的初始状态为完全逆序，如[5,4,3,2,1]，每一轮外层循环都要将当前为排序部分的最大元素冒泡到正确位置，而且每次比较都会发生交换，此时：
+
+- **比较次数**： 共需要进行*(n - 1) + (n - 2) + ...*（等差数列求和）。
+- **交换次数**： 每次比较均需要交换，总交换次数也为上式结果。
+
+
+