四、分治算法

1、求一组数据中最大的两个数

#include<stdio.h>
#define N 100001
int n;
int a[N];
void qs(int arr[], int low, int high) {
	if(low<high){
		int p=arr[high];
		int i=low-1;
		for(int j=low;j<high;j++){
			if(arr[j]<p){
				i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
			}
		}
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        int pinext = i + 1;

        qs(arr, low, pinext - 1);
        qs(arr, pinext + 1, high);
	}
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    qs(a, 1, n);

    printf("max1=%d max2=%d\n", a[n], a[n - 1]);
    printf("min1=%d min2=%d\n", a[1], a[2]);
    return 0;
}

2、求一组数据的和

#include "stdio.h"

/**********  Begin  **********/
int n,ans;
int main()
{
 	scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int numn;scanf("%d",&numn);
        ans+=numn;
    }
    printf("分治法求出数组元素的和为:%d",ans);
    return 0;
}
/**********  End  **********/

3、找出数组中第 k 个小的元素

#include<stdio.h>
#define N 100001
int n,m;
int a[N];
void qs(int arr[], int low, int high) {
	if(low<high){
		int p=arr[high];
		int i=low-1;
		for(int j=low;j<high;j++){
			if(arr[j]<p){
				i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
			}
		}
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        int pinext = i + 1;

        qs(arr, low, pinext - 1);
        qs(arr, pinext + 1, high);
	}
}
int main(){
    scanf("%d %d", &n,&m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    qs(a, 1, n);

    printf("第%d小的元素是%d",m,a[m]);
    return 0;
}