Ideas and examples of divide and conquer

Divide and conquer method

Quick sort

1. decompose a[s…t] Decompose into a[s…i-1] and a[i+1…t], among i Is the basis of division

2. Solving subproblems ： If the length of the subsequence is 0 Or for 1, Then he is orderly , Go straight back to ; Otherwise, each subproblem is solved recursively .

3. Merge ： Because the whole sequence is stored in an array a in , The sorting process is in place , The merge step does not require any action .

4. example ：

   int Partition(int a[],int s,int t){
         // Partition algorithm 
       int i=s,j=t;
       int tmp=a[s];  // Use the first record of the sequence as the benchmark 
       while(i!=j){
            // Scan alternately from both ends of the sequence to the middle , until i=j until 
           while(j>i&&a[j]>=tmp)
               j--;   // Scan from right to left for keywords less than tmp Of a[j]
           a[i]=a[j]; // take a[j] Migrate to a[i] Location 
           while(i<j&&a[i]<=tmp)
               i++;  // From left to right , The first keyword found is greater than tmp Of a[i]
           a[j]=a[i]; // take a[i] Move back to a[j] The location of 
       }
       a[i]=tmp;
       return i;
   } 
   /*{2,5,1,7,10,6,9,4,3,8}  With 2 Cardinal number   Two pointers : Left sub needle left, Right sub needle right  Search from right to left for numbers less than cardinality , Search from left to right for the number whose prime is greater than the benchmark  a[i]=a[j]; // take a[j] Migrate to a[i] Location  a[j]=a[i]; // take a[i] Move back to a[j] The location of  1<2 i=0,j=2 1,5,1,7,10,6,9,4,3,8  And then from left,5>2,j=3,i=1 1,5,5,7,10,6,9,4,3,8  Loop search  i=1,j=3  There is no less than cardinal number in the rear 2 The number of will i=1 Set as 2 1,2,5,7,10,6,9,4,3,8  perform QuikSort(a,s,i-1) i The left side of the does not change  i To the right of 5 Benchmarking   perform  QuickSort(a,i+1,t);// */
   void QuikSort(int a[],int s,int t){
         
       if(s<t){
         
           int i=Partition(a,s,t);
           QuikSort(a,s,i-1);// Recursively sort the left subsequence 
           QuickSort(a,i+1,t);// Recursive sorting of right subsequences 
       }
   }
   

5. Seek before k individual

   void QuickSort(T a[],int s,int t,int k){
         
       int i;
       if(s<t){
         
           i=Partition(a,s,t);
           if(k<i+1)
              QuickSort(a,s,i-1,k);
           else if(k>i+1)
               QuickSort(A,i+1,k)
       }
   }
   T solve(T a[],int n,int k){
         
       QuickSort(a,0,n-1,k);
       for(int i=0;i<k;i++)
           printf("%d",a[i]);
       printf("\n");
   }
   

Merge sort

1. take a[0…n-1] as n A length of 1 The order sheet , Will be adjacent to k（k>=2） An ordered list is merged in pairs , obtain k/n A length of k The ordered sub table of ; Then we continue to merge the western Zhejiang ordered subsequences , obtain n/k Ordered sub table of the square of , It goes on and on , Finally, we get a length of n The order sheet ,k by 2 It is a two-way merge sort

2. example ：

   2,5,1,7,10,6,9,4,3,8
   2,5 1,7 10,6 9,4 3,8
   1,2,5,7 4,6,9,10 3,8
   1,2,4,5,6,7,9,10 3,8
   1,2,3,4,5,6,7,8,9,10
   

3. The divide and conquer strategy is as follows :

   1. loop log2 n,length Take... In turn 1、2、4、.... Each time, execute the following
   2. decompose ： Decompose the original sequence into length Some subsequences of length
   3. Merge ： Call two adjacent subsequences Merge Algorithm sorting produces an ordered subsequence

4. Algorithm design :

   1. Bottom up

   void Merge(int a[],int low ,int mid ,int high)
   {
         
       int *tmpa;
       int i=low,j=mid+1,k=0;
       tmpa=(int *)malloc((hight-low+1)*sizeof(int));
       while(i<=mid&&j<=high)
       {
         
           if(a[i]<=a[j])// Put the elements in the first child table into tmpa
           {
         
               tmpa[k]=a[i];
               i++;
               k++;
           }
           else
           {
         
               tmpa[k]=a[j];// Put the elements in the second sub table into tmpa
               j++;
               k++;
           }
       }
       while(i<=mid)// Copy the rest of the first sub table to tmpa
       {
         tmpa[k]=a[i];i++;k++}
       while(j<=high)// Copy the rest of the second sub table to tmpa
       {
         tmpa[k]=a[j];j++;k++}
       for(k=0;i=low;i<=high;k++,i++)// take tmpa Copy back a in 
           a[i]=tmpa[k];
       free(tmpa);// Release tmpa Occupied memory space 
   }
   void MergePass(int a[],int length,int n)
   {
         
       int i;
       for(int i=0;i+2*length-1<n;i=i+2*length)// Merger length Long two-phase adjacent sub table 
           Merge(a,i,i+length-1,i+2*length-1);
       if(i+length-1<n) // The remaining two sub tables , The latter is less than length
           Merge(a,i,i+length-1,n-1);// Merge these two sub tables 
   }
   void MergeSort(int a[],int n)
   {
         
       int length;
       for(length=1;length<n;length=2*lenth)
           MergePass(a,length,n);
   }
   

   2. The top-down

   /*2,5,1,7,10,6,9,4,3,8 2,5,1,7,10 6,9,4,3,8 2,5,1 7,10 6,9,4 3,8 2,5 1 7,10 6,9 4 3 8 2 5 7 10 6 9 2,5 6,9 1,2,5 4,6,9 1,2,5,7,10 3,4,6,8,9 1,2,3,4,5,6,7,8,9 */
   void MergeSort(int a[],int low,int high)
   {
         
       int mid;
       if(low<high)// A subsequence has two or more elements 
       {
         
           mid=(low+high)/2;// Take the middle position 
           MergeSort(a,low,mid);// Yes a[low..mid] Subsequence sorting 
           MergeSort(a,mid+1,high);// Yes a[mid+1...high] Subsequence sorting 
           Merge(a,low,mid,high);// Merge two subsequences , See the previous algorithm 
       }
   }
   

5. Find the maximum and the second largest

   1. decompose ： Press the middle position mid=(low+high)/2 Divided into a[low…mid] and a[mid+1…high] Left and right intervals ( Note that the left section contains a[mid])

   2. Solve the decomposition subproblem ： Find the maximum value of the left interval lmax1 And the second largest value lmax2, Find the maximum value of the right interval rmax1 And the second largest value rmax2

   3. Merge ： if lmax1>rmax1, be max1=lmax1,max2=MAX{lmax2,rmax1}m otherwise max1=rmax1,max2={

      lmax1,rmax2}

   #include<algorithm>
   #include<iostream>
   #include<stdio.h>
   using namespace std;
   #define INF 600000;
   // stay vs6 in max want _cpp_max
   void solve(int a[],int low,int high,int &max1,int &max2)
   {
         
   	if(low==high)  // There is only one element in the interval 
   	{
         
   		max1=a[low];
   		max2=-INF;
   	}
   	else if(low==high-1) // The interval has only two elements 
   	{
         
   		max1=_cpp_max(a[low],a[high]);
   		max2=_cpp_min(a[low],a[high]);
   	}
   	else
   	{
         
   
   		int mid=(low+high)/2;// An interval has more than two elements 
   		int lmax1,lmax2;
   		solve(a,low,mid,lmax1,lmax2);// Left interval lmax1 and lmax2
   		int rmax1,rmax2;
   		solve(a,mid+1,high,rmax1,rmax2);// Find the right interval rmax1 and rmax2
   		if(lmax1>rmax1)
   		{
         
   			max1=lmax1;
   			max2=_cpp_max(lmax2,rmax1);//lmax2,rmax1 Find the next largest element in 
   		}
   		else
   		{
         
   			max1=rmax1;
   			max2=_cpp_max(lmax1,rmax2); //lmax1、rmax Find the next largest element in 
   		}
   	}
   }
   
   

6. Binary search