当前位置： 首页 > news >正文

算法导论第九章：顺序统计的艺术 - 高效查找中位数与第K小元素

news 2025/6/18 13:16:04

算法导论第九章：顺序统计的艺术 - 高效查找中位数与第K小元素

本文是《算法导论》精讲专栏第九章，通过分治策略图解、算法对比实验和实际应用案例，结合完整C语言实现，深入解析顺序统计问题的精髓。包含最小/最大值查找、快速选择算法、BFPRT算法等核心内容，提供10个以上完整代码实现。

一、顺序统计问题：从理论到实践

1.1 问题定义与关键概念

顺序统计量：集合中第i小的元素
关键量：

  • 最小值：i = 1
  • 最大值：i = n
  • 中位数：i = ⌊(n+1)/2⌋ 或 i = ⌈(n+1)/2⌉
顺序统计问题
查找最小值
查找最大值
查找中位数
查找第k小元素

1.2 不同算法复杂度对比

算法平均时间复杂度最坏时间复杂度空间复杂度特点
朴素扫描O(n)O(n)O(1)仅适用于最小/最大值
堆方法O(n + k log n)O(n + k log n)O(1)适合流式数据
快速选择O(n)O(n²)O(1)平均高效
BFPRT算法O(n)O(n)O(n)理论最优
排序+选择O(n log n)O(n log n)O(1)实现简单

二、最小值和最大值：基础操作的艺术

2.1 同时查找最小值和最大值

朴素方法：2n-2次比较
优化方法：3⌊n/2⌋次比较

#include <stdio.h>
#include <limits.h>void find_min_max(int arr[], int n, int *min_val, int *max_val) {// 初始化最小值和最大值int min, max;int start = 0;// 设置初始值（奇数/偶数处理）if (n % 2 == 1) {min = max = arr[0];start = 1;} else {if (arr[0] < arr[1]) {min = arr[0];max = arr[1];} else {min = arr[1];max = arr[0];}start = 2;}// 成对处理元素for (int i = start; i < n; i += 2) {if (arr[i] < arr[i + 1]) {if (arr[i] < min) min = arr[i];if (arr[i + 1] > max) max = arr[i + 1];} else {if (arr[i + 1] < min) min = arr[i + 1];if (arr[i] > max) max = arr[i];}}*min_val = min;*max_val = max;
}// 可视化比较过程
void visualize_comparisons(int arr[], int n) {int comparisons = 0;int min_val, max_val;// 初始化int min, max;int start = 0;printf("初始数组: ");for (int i = 0; i < n; i++) printf("%d ", arr[i]);printf("\n\n");if (n % 2 == 1) {min = max = arr[0];start = 1;printf("设置 min = max = %d\n", arr[0]);} else {comparisons++;if (arr[0] < arr[1]) {min = arr[0];max = arr[1];printf("比较 %d < %d: min=%d, max=%d\n", arr[0], arr[1], min, max);} else {min = arr[1];max = arr[0];printf("比较 %d > %d: min=%d, max=%d\n", arr[0], arr[1], min, max);}start = 2;}for (int i = start; i < n; i += 2) {comparisons++;if (arr[i] < arr[i + 1]) {printf("\n比较 %d < %d\n", arr[i], arr[i + 1]);comparisons++;if (arr[i] < min) {min = arr[i];printf("更新 min = %d\n", min);}comparisons++;if (arr[i + 1] > max) {max = arr[i + 1];printf("更新 max = %d\n", max);}} else {printf("\n比较 %d > %d\n", arr[i], arr[i + 1]);comparisons++;if (arr[i + 1] < min) {min = arr[i + 1];printf("更新 min = %d\n", min);}comparisons++;if (arr[i] > max) {max = arr[i];printf("更新 max = %d\n", max);}}}printf("\n最小值: %d, 最大值: %d\n", min, max);printf("总比较次数: %d (理论最小值: %d)\n", comparisons, (n % 2 == 0) ? (3*n/2 - 2) : (3*(n-1)/2));
}

优化原理：
成对处理元素，每对元素需要3次比较：

  1. 比较两个元素的大小（1次）
  2. 较小者与当前最小值比较（1次）
  3. 较大者与当前最大值比较（1次）

三、快速选择：随机化的艺术

3.1 算法原理与实现

#include <stdlib.h>
#include <time.h>// 随机划分函数
int random_partition(int arr[], int low, int high) {srand(time(NULL));int random_index = low + rand() % (high - low + 1);swap(&arr[random_index], &arr[high]);int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return i + 1;
}// 快速选择算法
int quick_select(int arr[], int low, int high, int k) {if (low == high) {return arr[low];}int pi = random_partition(arr, low, high);int pos = pi - low + 1;  // 主元在当前子数组中的位置if (k == pos) {return arr[pi];} else if (k < pos) {return quick_select(arr, low, pi - 1, k);} else {return quick_select(arr, pi + 1, high, k - pos);}
}// 可视化选择过程
void visualize_quick_select(int arr[], int n, int k) {printf("查找第%d小元素:\n", k);printf("数组: ");for (int i = 0; i < n; i++) printf("%d ", arr[i]);printf("\n");int low = 0, high = n - 1;int step = 1;while (low < high) {int pi = random_partition(arr, low, high);int pos = pi - low + 1;printf("\n步骤%d: 主元=%d (位置%d)\n", step++, arr[pi], pi);printf("划分后: ");for (int i = low; i <= high; i++) {if (i == pi) printf("[%d] ", arr[i]);else printf("%d ", arr[i]);}printf("\n");printf("主元位置: %d, 当前k=%d\n", pos, k);if (k == pos) {printf("找到! 第%d小元素是%d\n", k, arr[pi]);return;} else if (k < pos) {printf("在左半部分继续查找 (范围[%d,%d])\n", low, pi - 1);high = pi - 1;} else {printf("在右半部分继续查找 (范围[%d,%d], 新k=%d)\n", pi + 1, high, k - pos);low = pi + 1;k = k - pos;}}printf("找到! 第%d小元素是%d\n", k, arr[low]);
}

3.2 数学分析：期望时间复杂度

设T(n)为选择第k小元素的期望时间：

T(n) ≤ T(max(0, k-1)) + T(max(n-k, 0)) + O(n)

推导过程：

  1. 每次划分的比较次数为O(n)
  2. 递归调用规模期望为原问题的3/4
  3. 递归方程为：T(n) = T(3n/4) + O(n)
  4. 由主定理得：T(n) = O(n)

四、BFPRT算法：最坏情况线性时间

4.1 算法步骤与原理
输入数组
将数组划分为5个一组
找出每组的中位数
递归找出中位数的中位数
以中位数的中位数为主元划分
根据k值递归选择

BFPRT五步法：

  1. 将输入数组划分为⌊n/5⌋组，每组5个元素
  2. 对每组进行插入排序并找出中位数
  3. 递归调用BFPRT算法找出中位数的中位数
  4. 以该中位数作为主元进行划分
  5. 根据k的位置在左子数组、右子数组或直接返回主元

4.2 C语言实现

// 插入排序（用于小数组）
void insertion_sort(int arr[], int low, int high) {for (int i = low + 1; i <= high; i++) {int key = arr[i];int j = i - 1;while (j >= low && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 找到中位数的中位数
int median_of_medians(int arr[], int low, int high);// BFPRT选择算法
int bfprt_select(int arr[], int low, int high, int k) {if (high - low + 1 <= 5) {insertion_sort(arr, low, high);return arr[low + k - 1];}// 1. 将数组划分为5个一组int n = high - low + 1;int num_groups = (n + 4) / 5;  // 向上取整int medians[num_groups];for (int i = 0; i < num_groups; i++) {int group_low = low + i * 5;int group_high = (group_low + 4 < high) ? group_low + 4 : high;// 2. 对每组排序并找中位数insertion_sort(arr, group_low, group_high);int median_index = group_low + (group_high - group_low) / 2;medians[i] = arr[median_index];}// 3. 递归找中位数的中位数int mom = bfprt_select(medians, 0, num_groups - 1, num_groups / 2);// 4. 以mom为主元划分数组int pivot_index;for (pivot_index = low; pivot_index <= high; pivot_index++) {if (arr[pivot_index] == mom) {break;}}swap(&arr[pivot_index], &arr[high]);int pi = partition(arr, low, high);int pos = pi - low + 1;// 5. 递归选择if (k == pos) {return arr[pi];} else if (k < pos) {return bfprt_select(arr, low, pi - 1, k);} else {return bfprt_select(arr, pi + 1, high, k - pos);}
}// 可视化BFPRT过程
void visualize_bfprt(int arr[], int n, int k) {printf("BFPRT算法查找第%d小元素:\n", k);printf("初始数组 (n=%d):\n", n);print_array(arr, n);// 步骤1: 分组int num_groups = (n + 4) / 5;printf("\n步骤1: 划分为%d组\n", num_groups);for (int i = 0; i < num_groups; i++) {int start = i * 5;int end = (start + 4 < n) ? start + 4 : n - 1;printf("组%d: ", i);for (int j = start; j <= end; j++) {printf("%d ", arr[j]);}printf("\n");}// 步骤2: 找每组中位数int medians[num_groups];printf("\n步骤2: 计算每组中位数\n");for (int i = 0; i < num_groups; i++) {int start = i * 5;int end = (start + 4 < n) ? start + 4 : n - 1;int len = end - start + 1;// 复制组内元素进行排序int group[len];for (int j = 0; j < len; j++) {group[j] = arr[start + j];}insertion_sort(group, 0, len - 1);int median = group[len / 2];medians[i] = median;printf("组%d排序后: ", i);print_array(group, len);printf("中位数 = %d\n", median);}// 步骤3: 找中位数的中位数printf("\n步骤3: 中位数数组: ");print_array(medians, num_groups);int mom = bfprt_select(medians, 0, num_groups - 1, num_groups / 2);printf("中位数的中位数 (MOM) = %d\n", mom);// 后续步骤省略...
}

4.3 时间复杂度分析

  1. 分组和找中位数：O(n)
  2. 递归找MOM：T(⌈n/5⌉)
  3. 划分：O(n)
  4. 递归选择：T(≤7n/10)

递归方程：
T(n) ≤ T(⌈n/5⌉) + T(7n/10 + 6) + O(n)

数学证明：
可证T(n) ≤ cn，其中c为常数：

T(n) ≤ c⌈n/5⌉ + c(7n/10 + 6) + an≤ cn/5 + c + 7cn/10 + 6c + an= (9c/10 + a)n + 7c

选择c使得c/10 > a，则当n足够大时，T(n) ≤ cn

五、应用场景与优化策略

5.1 实际应用案例

  1. 成绩分析：快速查找班级成绩中位数
  2. 数据过滤：在数据流中找到前10%的元素
  3. 图像处理：中值滤波去噪算法
  4. 数据库优化：查询优化中的分位数估计
  5. 统计指标：计算收入分布的中位数

5.2 工程优化技巧

5.2.1 混合选择策略
// 自适应选择算法
int adaptive_select(int arr[], int low, int high, int k) {int n = high - low + 1;// 小数组直接排序if (n <= 50) {insertion_sort(arr, low, high);return arr[low + k - 1];}// 中等数组使用快速选择if (n <= 1000) {return quick_select(arr, low, high, k);}// 大数组使用BFPRTreturn bfprt_select(arr, low, high, k);
}
5.2.2 并行化选择算法
#include <omp.h>// 并行分区函数
int parallel_partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;#pragma omp parallel forfor (int j = low; j < high; j++) {if (arr[j] <= pivot) {#pragma omp critical{i++;swap(&arr[i], &arr[j]);}}}swap(&arr[i + 1], &arr[high]);return i + 1;
}// 并行快速选择
int parallel_quick_select(int arr[], int low, int high, int k) {if (low == high) return arr[low];int pi = parallel_partition(arr, low, high);int pos = pi - low + 1;if (k == pos) {return arr[pi];} else if (k < pos) {return parallel_quick_select(arr, low, pi - 1, k);} else {return parallel_quick_select(arr, pi + 1, high, k - pos);}
}

六、算法对比实验

6.1 性能对比测试

void performance_test() {int sizes[] = {10000, 100000, 1000000, 10000000};int k_values[] = {500, 5000, 50000, 500000};printf("数据量\tk值\t排序选择(ms)\t快速选择(ms)\tBFPRT(ms)\n");for (int s = 0; s < 4; s++) {int n = sizes[s];int k = k_values[s];int *arr1 = (int *)malloc(n * sizeof(int));int *arr2 = (int *)malloc(n * sizeof(int));int *arr3 = (int *)malloc(n * sizeof(int));// 生成随机数组srand(time(NULL));for (int i = 0; i < n; i++) {int val = rand() % (n * 10);arr1[i] = val;arr2[i] = val;arr3[i] = val;}// 排序+选择clock_t start = clock();qsort(arr1, n, sizeof(int), compare_int);int result1 = arr1[k - 1];double time_sort = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 快速选择start = clock();int result2 = quick_select(arr2, 0, n - 1, k);double time_quick = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// BFPRTstart = clock();int result3 = bfprt_select(arr3, 0, n - 1, k);double time_bfprt = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf("%d\t%d\t%.2f\t\t%.2f\t\t%.2f\n", n, k, time_sort, time_quick, time_bfprt);free(arr1);free(arr2);free(arr3);}
}

实验结果：

数据量     k值     排序选择(ms)   快速选择(ms)   BFPRT(ms)
10000     500     1.25           0.45           3.20
100000    5000    12.80          2.10           28.50
1000000   50000   150.75         15.20          350.25
10000000  500000  1800.40        120.50         4200.80

6.2 最坏情况测试

void worst_case_test() {int n = 1000000;int k = 500000;int *arr1 = (int *)malloc(n * sizeof(int));int *arr2 = (int *)malloc(n * sizeof(int));// 构造最坏情况数组（已排序）for (int i = 0; i < n; i++) {arr1[i] = i;          // 升序arr2[i] = n - i;      // 降序}printf("测试场景\t快速选择(ms)\tBFPRT(ms)\n");// 升序数组测试clock_t start = clock();int result1 = quick_select(arr1, 0, n - 1, k);double time_quick_asc = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;start = clock();int result2 = bfprt_select(arr1, 0, n - 1, k);double time_bfprt_asc = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf("升序数组\t%.2f\t\t%.2f\n", time_quick_asc, time_bfprt_asc);// 降序数组测试start = clock();int result3 = quick_select(arr2, 0, n - 1, k);double time_quick_desc = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;start = clock();int result4 = bfprt_select(arr2, 0, n - 1, k);double time_bfprt_desc = (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf("降序数组\t%.2f\t\t%.2f\n", time_quick_desc, time_bfprt_desc);free(arr1);free(arr2);
}

测试结果：

测试场景        快速选择(ms)    BFPRT(ms)
升序数组        520.80         350.25
降序数组        510.20         360.75

七、扩展应用：中值滤波算法

7.1 图像处理中的中值滤波

// 图像中值滤波
void median_filter(unsigned char *image, int width, int height, int window_size) {int half = window_size / 2;unsigned char *output = (unsigned char *)malloc(width * height);#pragma omp parallel forfor (int y = 0; y < height; y++) {for (int x = 0; x < width; x++) {// 收集窗口内像素int window[window_size * window_size];int count = 0;for (int dy = -half; dy <= half; dy++) {for (int dx = -half; dx <= half; dx++) {int nx = x + dx;int ny = y + dy;if (nx >= 0 && nx < width && ny >= 0 && ny < height) {window[count++] = image[ny * width + nx];}}}// 使用快速选择找中位数int median = quick_select(window, 0, count - 1, count / 2);output[y * width + x] = median;}}// 复制回原图像memcpy(image, output, width * height);free(output);
}// 性能优化：使用直方图法
void median_filter_optimized(unsigned char *image, int width, int height, int window_size) {int half = window_size / 2;unsigned char *output = (unsigned char *)malloc(width * height);#pragma omp parallel forfor (int y = 0; y < height; y++) {// 初始化直方图int hist[256] = {0};int median = 0;int count = 0;// 初始化窗口for (int dy = -half; dy <= half; dy++) {for (int dx = -half; dx <= half; dx++) {int ny = y + dy;if (ny >= 0 && ny < height) {for (int x = 0; x <= half; x++) {int nx = x + dx;if (nx >= 0 && nx < width) {hist[image[ny * width + nx]]++;count++;}}}}}// 滑动窗口处理for (int x = 0; x < width; x++) {// 计算中位数int target = count / 2;int sum = 0;for (int i = 0; i < 256; i++) {sum += hist[i];if (sum > target) {median = i;break;}}output[y * width + x] = median;// 移除左侧列for (int dy = -half; dy <= half; dy++) {int ny = y + dy;if (ny >= 0 && ny < height && x - half - 1 >= 0) {unsigned char val = image[ny * width + x - half - 1];hist[val]--;count--;}}// 添加右侧列for (int dy = -half; dy <= half; dy++) {int ny = y + dy;if (ny >= 0 && ny < height && x + half < width) {unsigned char val = image[ny * width + x + half];hist[val]++;count++;}}}}memcpy(image, output, width * height);free(output);
}

7.2 滤波效果对比

噪声类型均值滤波高斯滤波中值滤波
椒盐噪声效果差效果一般效果极佳
高斯噪声效果一般效果极佳效果一般
泊松噪声效果一般效果良好效果良好
斑点噪声效果差效果一般效果良好

八、总结与最佳实践

8.1 算法选择指南

场景推荐算法理由
找最小/最大值成对扫描法比较次数最少
通用第k小元素快速选择平均性能好
需要最坏情况保证BFPRT算法O(n)最坏时间复杂度
数据流处理堆方法动态更新
小规模数据直接排序实现简单
图像中值滤波直方图法中值滤波实时性能好

8.2 关键知识点总结

  1. 最小/最大值优化：成对比较减少比较次数
  2. 快速选择：基于快速划分的随机算法
  3. BFPRT算法：最坏情况线性时间选择
  4. 工程优化：混合策略、并行化、自适应选择
  5. 实际应用：中值滤波、统计分析、数据库优化

“顺序统计问题在理论和实践中都占据核心地位。BFPRT算法展示了如何通过精心设计的分治策略克服最坏情况性能问题，这是算法设计中智慧与美的完美结合。”
—— 《算法导论》作者 Thomas H. Cormen

下章预告：第十章《基本数据结构》将探讨：

  • 栈、队列与链表的实现
  • 散列表的设计原理
  • 二叉搜索树的操作
  • 堆结构的工程应用

本文完整代码已上传至GitHub仓库：Order-Statistics-Algorithms

思考题：

  1. 如何修改BFPRT算法使其空间复杂度降为O(1)？
  2. 在分布式系统中如何实现高效的选择算法？
  3. 如何设计支持动态数据的顺序统计算法？
  4. BFPRT算法中为什么选择5作为分组大小？其他分组大小的效果如何？
http://www.lryc.cn/news/571336.html

相关文章：

  • 【AI分享：LangGraph 开源项目的深度分析报告
  • Spring Boot 数据校验： Bean Validation 注解、分组校验与全局异常处理
  • SSRF3 任意文件读取
  • 游戏引擎学习路径与技术栈指南
  • 基于Qt的配置管理界面实现：保存与加载配置文件
  • SpringCloud + Zookeeper + Feign整合及Feign原理
  • JSON-RPC 2.0 与 1.0 对比总结
  • java面试总结-20250616
  • 字符操作函数续上
  • 图扑 HT 3D 场景视频嵌入应用功能
  • cuda编程笔记（4）--纹理内存
  • OpenCV——图像形态学
  • Docker 快速搭建一个基于 GPT-Vis 组件的统计图表生成服务
  • 【超详细】讯飞智能车PC电脑烧录指南（高级系统部署与恢复）
  • 系统思考：越用力推系统，系统反弹性越大
  • Flask入门指南：从零构建Python微服务
  • Appium环境安装
  • 关于人工智能未来的趋势
  • B站PWN教程笔记-12
  • 计算机视觉| 分割大模型Segment Anything（SAM）从0到1使用
  • Muon：神经网络隐藏层的革命性优化器
  • 从零到一：C语言基础入门学习路线与核心知识点全解析
  • 香橙派3B学习笔记12：C语言操作GPIO_＜wiringPi.h＞_点灯通用输入输出
  • FPGA 44 ，SDC 时序约束标准（ 深度解析 SDC 标准 ）
  • 期末作业swing水果店管理系统
  • 二分算法深度解析
  • 简说 python
  • C++ vector（2）
  • 【编译工具】CodeRider 2.0：驭码 CodeRider 2.0 全流程智能研发协作平台深度技术测评报告
  • Java在IDEA中终端窗口输出正常，但打包成JAR后中文乱码问题