c++写一个找中位数的代码
时间: 2024-05-13 18:14:49 浏览: 30
以下是使用快速选择算法(Quickselect Algorithm)找到一个数组的中位数的 C 代码:
```c
#include <stdio.h>
// 快速选择算法
int quickSelect(int arr[], int left, int right, int k) {
if (left == right) {
return arr[left];
}
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left + k - 1 <= j) {
return quickSelect(arr, left, j, k);
}
if (left + k - 1 >= i) {
return quickSelect(arr, i, right, k - (i - left));
}
return arr[j + 1];
}
// 计算中位数
int median(int arr[], int n) {
if (n % 2 == 0) {
return (quickSelect(arr, 0, n - 1, n / 2) +
quickSelect(arr, 0, n - 1, n / 2 + 1)) / 2;
} else {
return quickSelect(arr, 0, n - 1, n / 2 + 1);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("数组的中位数为:%d", median(arr, n));
return 0;
}
```
该代码先使用快速选择算法找到数组中第 `n/2+1` 小的数,然后如果数组长度为偶数,再找到第 `n/2` 小的数,最后计算它们的平均值作为中位数。