【数据结构与算法】众数、中位数

今天学这个东西的时候，看到这种线性的数据结构加上排序步骤，很难不想写个程序来跑跑。 先来说说中位数，这个比较有思路。 中位数 具体的操作步骤应该是：排序 => 获得数据元素个数n => 是奇数 ? (n+1) / 2 : n / 2 那么排序就用之前学的冒泡排序，这种题目大概不会完全倒序给数据，编写sort函数： 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函数，判断奇偶性。 int is_even(int data) { if (data % 2 == 0) { return true; } else { return false; } } 完成了奇偶判断，下一步就可以正式进行中位数的运算，编写get_median函数。 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）是指在统计分布上具有明显集中趋势点的数值，代表数据的一般水平。 也是一组数据中出现次数最多的数值，有时众数在一组数中有好几个。用M表示。 那么，在程序中，想要计算一个值出现的次数并比对，可拆分为两步。 计算出每一个数据出现的次数 结果排序比对 找出最大值 我没学过什么高级的数据结构，就用这个复制数组的笨办法吧。 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 如果遇到新元素，检查是否需要更新最大值 动态更新众数值 测试跑一把，输出如下 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 这个办法实在是有点蠢，找时间仔细学学哈希表，应该能更快。