c语言求n个数的中位数
时间: 2024-01-29 19:02:40 浏览: 56
可以使用快速选择(QuickSelect)算法来求解。时间复杂度为O(n)。以下是C语言代码示例:
#include <stdio.h>
#define SWAP(a, b) { int t = (a); (a) = (b); (b) = t; }
int partition(int* arr, int left, int right)
{
int pivot = arr[left];
int l = left + 1;
int r = right;
while (l <= r)
{
if (arr[l] < pivot)
{
l++;
}
else if (arr[r] >= pivot)
{
r--;
}
else
{
SWAP(arr[l], arr[r]);
l++;
r--;
}
}
SWAP(arr[left], arr[r]);
return r;
}
int quick_select(int* arr, int left, int right, int k)
{
if (left == right)
{
return arr[left];
}
int pivot_index = partition(arr, left, right);
if (k == pivot_index)
{
return arr[k];
}
else if (k < pivot_index)
{
return quick_select(arr, left, pivot_index - 1, k);
}
else
{
return quick_select(arr, pivot_index + 1, right, k);
}
}
int main()
{
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int median = 0;
if (n % 2 == 1)
{
median = quick_select(arr, 0, n - 1, n / 2);
}
else
{
int left = quick_select(arr, 0, n - 1, n / 2 - 1);
int right = quick_select(arr, 0, n - 1, n / 2);
median = (left + right) / 2;
}
printf("%d\n", median);
return 0;
}