【分治 || 排序问题、查找问题、最大子序列和问题】

• 分治法
• • 选择排序
  • 冒泡排序
  • 快速排序
  • 二路归并
  • 查找最大和次大元素
  • 折半查找
  • 查找第K小元素
  • 寻找两个等长有序序列的中位数
  • 求最大连续子序列和

void SelectSort(int a[],int n,int i)
{
	int k;
	//递归出口
	if(i==n-1) return;
	else
	{
		k=i;
		for(int j=i+1;j 
时间复杂度：O(
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2)
 
冒泡排序 
void BubbleSort(int a[],int n,int i)
{
	bool flag;
	if(i==n-1) return;
	else
	{
		flag=false;
		for(int j=n-1;j>i;j--)
		{
			if(a[j] 
时间复杂度：O(
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2)
 
快速排序 
void QuickSort(int a[],int s,int t)
{
	if(si&&a[j]>=temp)
			j--;
		a[j]=a[i];
		while(i 
最好情况：O(
     
      
       
        
         n
        
        
         l
        
        
         o
        
        
         
          g
         
         
          2
         
        
        
         n
        
       
       
        nlog_2n
       
      
     nlog2​n)，最坏情况：O(
     
      
       
        
         
          n
         
         
          2
         
        
       
       
        n^2
       
      
     n2)
 
二路归并 
void Merge(int a[],int low,int mid,int high)
{
	int *tmp;
	tmp=(*int)malloc((high-low+1)*sizeof(int));
	int i=low,j=mid+1,k=0;
	while(i<=mid&&j<=high)
	{
		if(a[i] 
时间复杂度：O(
     
      
       
        
         n
        
        
         l
        
        
         o
        
        
         
          g
         
         
          2
         
        
        
         n
        
       
       
        nlog_2n
       
      
     nlog2​n)
 
查找最大和次大元素 
void Solve(int a[],int low,int high,int &max1,int &max2)
{
	if(low==high)
	{max1=a[low];max2=-INF;}
	else if(low==high-1)
	{max1=max(a[low],a[high]);max2=min(a[low],a[high]);}
	else
	{
		mid=(low+high)/2;
		int lmax1,lmax2,rmax1,rmax2;
		Solve(a,low,mid,lmax1,lmax2);
		Solve(a,mid+1,high,rmax1,rmax2);
		if(lmax1>rmax1)
		{
			max1=lmax1;
			max2=max(lmax2,rmax1);
		}
		else
		{
			max1=rmax1;
			max2=max(lmax1,rmax2);
		}
	}
}
 
时间复杂度：O(
     
      
       
        
         n
        
       
       
        n
       
      
     n)
 
折半查找 
int BinarySearch(int a[],int low,int high,int k)
{
	if(lowk)
			return BinarySearch(a,low,mid-1,k);
		else
			return BinarySearch(a,mid+1,high,k);
	}
	else return -1;
}
 
时间复杂度：O(
     
      
       
        
         l
        
        
         o
        
        
         
          g
         
         
          2
         
        
        
         n
        
       
       
        log_2n
       
      
     log2​n)
 
查找第K小元素 
int QuickSelect(int a[],int s,int t,int k)
{
	int i=s,j=t;
	int tmp=a[s];
	if(si&&a[j]>=tmp) j--;
			a[i]=a[j];
			while(i 
时间复杂度：O(
     
      
       
        
         n
        
       
       
        n
       
      
     n)
 
寻找两个等长有序序列的中位数 
int midnum(int a[],int s1,int t1,int b[],int s2,int t2)
{
	int m1,m2;
	if(s1==t1&&s2=t2)
		return a[s1] 
时间复杂度：O(
     
      
       
        
         n
        
       
       
        n
       
      
     n)
 
求最大连续子序列和 
long maxSubSum(int a[],int left,int right)
{
	int i,j;
	long maxLeftSum,maxRightSum;
	long maxLeftBorderSum,leftBorderSum;
	long maxRightBorderSum,rightBorderSum;
	if(left==right)
	{
		if(a[left]>0)
			return a[left];
		else;
			return 0;
	}
	int mid=(left+right)/2; //求中间位置
　　 maxLeftSum= (a，left，mid); //求左边
　　 maxRightSum= (a，mid+1，right); //求右边
　　 maxLeftBorderSum=0，leftBorderSum=0;
　　 for (i=mid;i>=left;i--)　//求出以左边加上a[mid]元素
　　 { 
　　 	leftBorderSum+=a[i];　//构成的序列的最大和
　 		if (leftBorderSum>maxLeftBorderSum)
　　　　　	maxLeftBorderSum=leftBorderSum;
　　}
　　maxRightBorderSum=0，rightBorderSum=0;
　　for (j=mid+1;j<=right;j++) //求出a[mid]右边元素
　　{ 
　　		rightBorderSum+=a[j]; //构成的序列的最大和
　　 	if (rightBorderSum>maxRightBorderSum)
　　　　　	maxRightBorderSum=rightBorderSum;
　　}
　　return max3(maxLeftSum，maxRightSum，
	maxLeftBorderSum+maxRightBorderSum);
}
 
时间复杂度：O(
     
      
       
        
         n
        
        
         l
        
        
         o
        
        
         
          g
         
         
          2
         
        
        
         n
        
       
       
        nlog_2n
       
      
     nlog2​n)