首页 > 代码库 > 基础算法 分治法求最大最小元
基础算法 分治法求最大最小元
思路:运用分治的思想,将要排序的整个数组从中间劈开,分别求其左右两边的最大最小值,然后将求出的最大最小值合起来进行比较。
当左右两边的数组小到一定程度时:
(1)数组中只有一个元素,maxNum=minNum;
(2)数组中有两个元素,找出两个元素中的最大最小值;
(3)数组中大于两个元素,从中间分开,继续递归;
1 #include<stdio.h> 2 #include<iostream> 3 #include<stdlib.h> 4 using namespace std; 5 6 int arr[10]; 7 void getMax_Min(int left,int right,int &maxNum,int &minNum){ 8 if(left==right){ 9 maxNum=arr[left]; 10 minNum=arr[left]; 11 return ; 12 }else if(left+1==right){ 13 maxNum=arr[left]>arr[right]?arr[left]:arr[right]; 14 minNum=arr[left]>arr[right]?arr[right]:arr[left]; 15 return ; 16 }else{ 17 int mid=(left+right)/2; 18 int leftMax,leftMin,rightMax,rightMin; 19 getMax_Min(left,mid,leftMax,leftMin);//递归找出左边的最大最小值 20 getMax_Min(mid,right,rightMax,rightMin);//递归找出右边的最大最小值 21 maxNum=max(leftMax,rightMax);//左右两边最大值相比较,取最大的 22 minNum=min(leftMin,rightMin);//左右两边最小值相比较,取最小的 23 } 24 } 25 26 int main(){ 27 for(int i=0;i<10;i++){ 28 arr[i]=rand();//生成随机数 29 cout<<arr[i]<<" "; 30 } 31 cout<<endl; 32 int maxNum,minNum; 33 getMax_Min(0,9,maxNum,minNum); 34 cout<<"最大值是:"<<maxNum<<" 最小值是:"<<minNum<<endl; 35 return 0; 36 }
基础算法 分治法求最大最小元
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。