1 files changed, 137 insertions, 0 deletions
diff --git a/content/posts/【数据结构与算法】众数、中位数.md b/content/posts/【数据结构与算法】众数、中位数.md
new file mode 100644
index 0000000..83e1ed8
--- /dev/null
+++ b/content/posts/【数据结构与算法】众数、中位数.md
@@ -0,0 +1,137 @@
+---
+abbrlink: 2344272299
+categories:
+- 往昔
+date: "2025-05-27 19:41:53"
+tags:
+- 数据结构与算法
+title: 【数据结构与算法】众数、中位数
+---
+今天学这个东西的时候，看到这种线性的数据结构加上排序步骤，很难不想写个程序来跑跑。
+
+先来说说中位数，这个比较有思路。
+
+## 中位数
+
+具体的操作步骤应该是：**排序 => 获得数据元素个数n => 是奇数 ? (n+1) / 2 : n / 2**
+
+
+那么排序就用之前学的冒泡排序，这种题目大概不会完全倒序给数据，编写sort函数：
+
+```c
+void sort(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;
+      }
+    }
+  }
+}
+```
+
+接下来是判断奇偶，奇偶的判断非常简单，对取模运算的值比对就可以，编写is_even函数，判断奇偶性。
+```c
+int is_even(int data)
+{
+  if (data % 2 == 0) {
+    return true;
+  } else {
+    return false;
+  }
+}
+```
+
+完成了奇偶判断，下一步就可以正式进行中位数的运算，编写get_median函数。
+```c
+double get_median(int arr[], int length)
+{
+  // 获取索引
+  double result = 0;
+  sort(arr, length);
+  if (is_even(length)) {
+    int median_index_1 = arr[(length / 2) - 1];
+    int median_index_2 = arr[length / 2];
+    // 计算数据
+    result = (median_index_1 + median_index_2) / 2.0;
+  } else {
+    result = arr[length / 2];
+  }
+
+  return result;
+}
+```
+
+这个函数首先计算了中位数在数组的哪个索引，然后进行了计算。
+
+
+## 众数
+
+众数（Mode）是指在[统计分布](https://baike.baidu.com/item/%E7%BB%9F%E8%AE%A1%E5%88%86%E5%B8%83/8478867?fromModule=lemma_inlink)上具有明显集中趋势点的[数值](https://baike.baidu.com/item/%E6%95%B0%E5%80%BC/2013853?fromModule=lemma_inlink)，代表[数据](https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE/33305?fromModule=lemma_inlink)的一般水平。 也是一组数据中出现次数最多的数值，有时众数在一组数中有好几个。用M表示。
+
+那么，在程序中，想要计算一个值出现的次数并比对，可拆分为两步。
+
+1. 计算出每一个数据出现的次数
+2. 结果排序比对
+3. 找出最大值
+
+我没学过什么高级的数据结构，就用这个复制数组的笨办法吧。
+
+```c
+int get_mode(int arr[], int length)
+{
+  int *copy_arr = malloc(length * sizeof(int));
+  memcpy(copy_arr, arr, length * sizeof(int));
+  sort(copy_arr, length);
+
+  int max_count = 0;
+  int current_count = 1;
+  int mode = copy_arr[0];
+
+  for (int i = 1; i < length; i++) {
+    if (copy_arr[i] == copy_arr[i - 1]) {
+      current_count++;
+    } else {
+      if (current_count > max_count) {
+        max_count = current_count;
+        mode = copy_arr[i - 1];
+      }
+      current_count = 1;
+    }
+  }
+
+  if (current_count > max_count) {
+    mode = copy_arr[length - 1];
+  }
+
+  free(copy_arr);
+  return mode;
+}
+```
+
+这个函数干了以下几件事：
+- 复制数组
+- 排序复制好的数组
+- 对比数组元素，如果array[i] == array[i - 1]，出现次数+1
+- 如果遇到新元素，检查是否需要更新最大值
+- 动态更新众数值
+
+测试跑一把，输出如下
+```c
+int main()
+{
+  int arr[] = {1, 1, 1, 1, 2, 2, 4, 5, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2};
+  int length = sizeof(arr) / sizeof(arr[0]);
+  int result = get_mode(arr, length);
+  printf("result = %d\n", result);
+}
+```
+
+```
+result = 4
+```
+
+~~这个办法实在是有点蠢，找时间仔细学学哈希表，应该能更快。~~