I'm very glad to be able to start learning the data structure in my spare time today. I use Mr. Deng Junhui's videos and books to teach more

The function of the code is to find the largest and the next largest number in the array. In the following code, as long as max2? 3 is not called, it can run correctly [funny]

#include <iostream>

using namespace std;

void max2_1(int A[],int lo,int hi,int& x1,int& x2); 

void max2_2(int A[],int lo,int hi,int& x1,int& x2);

int main()

{

	int a[5] = {10,50,0,9,60};

	int max=0,submax=0;

	max2_2(a,0,4,max,submax);

	cout<<max<<" "<<submax<<endl;

	return 0;

}

//It seems that this code doesn't consider that the first element of the array is the maximum value

//Step 1: suppose the first value is the maximum value x1, and then compare backward one by one, so that you can find the maximum number X1 in the array 

//Step 2: suppose the first is the next largest number x2, and then compare backward one by one until the previous one of x1 

//Step 3: compare with x2 one by one from the next of x1, and take the larger one as the new x2 

void max2_1(int A[],int lo,int hi,int &x1,int &x2)

{

	x1 = lo;

	for(int i = lo+1;i<=hi;i++)//Consider the number of times the algorithm needs to be compared, n-1 (starting from lo+1)

		if(A[i]>A[x1]) x1 = i;

	x2 = lo;

	for(int i = lo+1;i<x1;i++)//The number of times this cycle and the next cycle need to be compared is n-2 (because x1 is removed once less)

		if(A[i]>A[x2]) x2 = i;

	for(int i = x1+1;i<=hi;i++)

		if(A[i]>A[x2]) x2 = i;

}//So the total algorithm complexity can be understood as 2n-3



//Step 1: compare the first two to get x1 and x2,x1 is max, x2 is submax

//The second part: scan forward, compare with x2. If it is larger than X2, replace the position of x2 and compare with x1

void max2_2(int A[],int lo,int hi,int& x1,int& x2)

{

	if(A[x1 = lo]<A[x2 = lo+1]) swap(x1,x2);//Here's a comparison

	for(int i = lo+2;i<=hi;i++)

	{

		if(A[x2]<A[i])//Switching times change from i to n-2 (starting from lo+2)

		{

			if(A[x1]<A[x2=i])//In the worst case, if hit conditions should also be compared n-2 times. The best is that if does not hit once

				swap(x1,x2);

		}

	}

}//So the best complexity of this algorithm is n-1, and the worst is 2n-3



//Therefore, it is found that there is no substantial improvement in max2 and max2. Let's take a look at the strategy of divide and rule, see max2 and max2

void max2_3(int A[],int lo,int hi,int& x1,int& x2)

{

	if(lo+2 == hi){/*...*/}

	if(lo+3 == hi){/*...*/}

	int mi = (lo+hi)/2;

	int x1L,x2L;max2_3(A,lo,mi,x1L,x2L);

	int x1R,x2R;max2_3(A,mi,hi,x1R,x2R);

	if(A[x1L]>A[x1R])

	{

		x1 = x1L;x2 = (A[x2L]>A[x1R]?x2L:x1R);

	}

	else

	{

		x1 = x1R;x2 = (A[x1L]>A[x2R]?x1L:x2R);

	}

}

I'm mainly worried that I can't hold on to it in the future. Let's see how long it will take for me to finish the video + book over and over again, 2333