1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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
```
~~这个办法实在是有点蠢，找时间仔细学学哈希表，应该能更快。~~
|
