用C语言实现以下功能:给定n个数字,找出前m大的数字。 输入 多组输入,每组输入格式如下。 第一行包含两个整数n m。(n<=100000, m>0) 第二行包含n个正整数。 输出 输出前m大的数字,若m>n输出ERROR。每组输出占一行。要求不能使用qsort函数
时间: 2024-02-12 19:04:07 浏览: 174
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 100000
int num[MAX_N]; // 定义一个全局数组,避免频繁开辟内存空间
void swap(int *a, int *b) { // 交换两个数的值
int temp = *a;
*a = *b;
*b = temp;
}
// 快速排序的分区函数
int partition(int left, int right) {
int pivot = num[right]; // 选择最后一个数作为枢轴
int i = left - 1;
for (int j = left; j < right; j++) {
if (num[j] >= pivot) { // 如果当前数大于等于枢轴,就将它与i+1位置的数交换
i++;
swap(&num[i], &num[j]);
}
}
swap(&num[i + 1], &num[right]); // 最后将枢轴与i+1位置的数交换
return i + 1;
}
// 快速排序的递归函数
void quick_sort(int left, int right, int m) {
if (left >= right) { // 递归结束的条件
return;
}
int mid = partition(left, right); // 分区
if (mid == m - 1) { // 如果mid恰好为m-1,说明前m大的数已经排好序了,直接返回
return;
} else if (mid < m - 1) { // 如果mid小于m-1,说明前m大的数在右边,继续对右边进行快速排序
quick_sort(mid + 1, right, m);
} else { // 如果mid大于m-1,说明前m大的数在左边,继续对左边进行快速排序
quick_sort(left, mid - 1, m);
}
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m) == 2) { // 不断读入输入,直到读到文件结尾
if (m > n) { // 如果m大于n,输出ERROR并跳过当前输入
printf("ERROR\n");
continue;
}
for (int i = 0; i < n; i++) {
scanf("%d", &num[i]); // 读入n个数字
}
quick_sort(0, n - 1, m); // 对数组进行快速排序
for (int i = 0; i < m; i++) { // 输出前m大的数字
printf("%d\n", num[i]);
}
}
return 0; // 程序结束
}
```
代码思路解析:
首先,我们使用了 `scanf` 函数来读取输入。由于有多组输入,我们使用了 `while` 循环来重复读取输入。为了避免频繁开辟内存空间,我们定义了一个全局数组 `num` 来存储输入的数字。
然后,我们判断如果 `m` 大于 `n`,就输出 `ERROR` 并跳过当前输入,否则就对数组进行快速排序。由于题目要求不能使用 `qsort` 函数,我们需要手动实现快速排序。快速排序的核心是分区函数,我们选择最后一个数作为枢轴,将数组分为两个部分,左边的数都小于枢轴,右边的数都大于枢轴。分区函数的代码如下:
```c
int partition(int left, int right) {
int pivot = num[right]; // 选择最后一个数作为枢轴
int i = left - 1;
for (int j = left; j < right; j++) {
if (num[j] >= pivot) { // 如果当前数大于等于枢轴,就将它与i+1位置的数交换
i++;
swap(&num[i], &num[j]);
}
}
swap(&num[i + 1], &num[right]); // 最后将枢轴与i+1位置的数交换
return i + 1;
}
```
接着,我们使用递归函数进行快速排序。当递归结束时,数组中前 `m` 大的数已经排好序了,我们只需要输出前 `m` 个数即可。需要注意的是,在递归过程中,我们需要判断枢轴的位置与 `m` 的大小关系,以决定是对左边进行快速排序还是对右边进行快速排序。具体实现可以参考代码。
最后,我们输出前 `m` 大的数字即可。需要注意的是,我们在交换两个数的值时,使用了一个辅助函数 `swap`。
阅读全文