c语言查找最大和次大元素:对于给定的含有n元素的无序序列,编写一个实验程序采用分治法求这个序列中最大和次大的两个不同的元素。 例如:(2, 5, 1, 4, 6, 3),最大元素为6,次大元素为5。
时间: 2024-09-30 14:06:43 浏览: 55
在C语言中,我们可以使用一种称为“快速选择”(QuickSelect)的算法,它是快速排序的一个变体,用于寻找数组中的第k小(或大)元素。这里我们稍微修改下思路,找到最大值后,再从剩余元素中找出第二大的。以下是简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 使用快速选择找第k小的元素
int partition(int arr[], int low, int high, int k) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j <= high - 1; j++) {
if (arr[j] > pivot) {
i++;
// 交换arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素移动到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 如果k等于i+1,说明找到了第k小的元素
if (k == i + 1)
return i + 1;
else if (k < i + 1)
// 需要在左半部分继续查找
return partition(arr, low, i, k);
else
// 需要在右半部分继续查找
return partition(arr, i + 2, high, k - i - 1);
}
// 找出最大和次大元素
void findLargestTwo(int arr[], int n) {
int maxIndex = partition(arr, 0, n - 1, n - 1);
int secondMaxIndex = partition(arr, 0, maxIndex - 1, maxIndex - 2);
printf("最大元素: %d\n", arr[maxIndex]);
printf("次大元素: %d\n", arr[secondMaxIndex]);
}
// 测试函数
int main() {
int arr[] = {2, 5, 1, 4, 6, 3};
int n = sizeof(arr) / sizeof(arr[0]);
findLargestTwo(arr, n);
return 0;
}
```
当运行上述代码,它会输出给定数组`{2, 5, 1, 4, 6, 3}`的最大元素6和次大元素5。
阅读全文