头歌资源库（20）最大最小数

一、问题描述

二、算法思想

使用分治法，可以将数组递归地分割成两部分，直到数组长度为1或2。然后比较这两部分的最大、次大、次小、最小数，最终得到整个数组中的最大两个数和最小两个数。

算法步骤如下：

定义一个函数 findMinMax(arr, start, end) ，用于在数组 arr 的下标范围 [start, end] 中寻找最大、次大、次小、最小数。
当 start 和 end 相等时，表示数组长度为1，直接返回这个数作为最大、次大、次小、最小数。
当 end 比 start 大1时，表示数组长度为2，比较这两个数的大小，返回较大的作为最大、次大数，较小的作为最小、次小数。
否则，将数组分成两等分，分别递归调用 findMinMax 函数，将得到的最大、次大、次小、最小数保存为 max1, max2, min1, min2 。
比较 max1 和 max2 ，较大的数为当前数组的最大数，较小的数为次大数。
比较 min1 和 min2 ，较小的数为当前数组的最小数，较大的数为次小数。
返回最大、次大、次小、最小四个数。

三、代码实现

#include <stdio.h>
 

 
void quicksort(int a[],int left,int right)
{
       if(left >= right) {
              return ;
       }
       int i = left;
       int j = right;
       int key = a[left];
 
       while(i < j) {
              while(i < j && key <= a[j]) {
                     j--;
              }
              a[i]= a[j];
              while(i < j && key >= a[i]) {
                     i++;
              }
              a[j]= a[i];
       }
       a[i]= key;
       quicksort(a,left,i- 1);
       quicksort(a,i+1,right);
}
 
int main()
{
       int i,N;       
       scanf("%d",&N);
       int num[N];
       for(i = 0; i < N; i++) {
              scanf("%d",&num[i]);
       }
 
       quicksort(num,0,N-1);
 
       printf("%-4d %-4d %-4d %-4d",num[N-1],num[N-2],num[1],num[0]);
       return 0;
}