C++程序设计-大模型思维与实践课件 第11章 递归-进阶内容

第十一章递归C++程序设计——大模型思维与实践1递归算法：回溯法3寻找纯素数1.问题描述例：有这样一种素数叫纯素数，当它是一个多位数的时候，把它的末位一位一位依次去掉之后余下的数依然是一个素数。例如2393，2393本身是一个素数，它的末位去掉之后，余下的239是一个素数，再将末位去掉，余下的23仍然是一个素数。再将末位去掉，余下的2依然是一个素数。请输出8位数的所有纯素数。2.问题分析枚举法：枚举法是一种直接而简单的方法，其核心思想是逐一尝试所有可能的情况，直到找到满足条件的解。对于寻找8位数的所有纯素数问题，枚举法会遍历所有8位的正整数，检查每一个数是否满足纯素数的定义：该数本身是素数，且去掉末位后剩余的数也是素数，直至只剩下一位（也需为素数）4寻找纯素数枚举法的缺点：效率低下：随着数字范围的增大，需要检查的数量急剧增加，导致算法运行时间显著增长。对于8位数的情况，虽然范围相对有限（10000000到99999999之间），但逐一检查每个数是否满足纯素数条件仍然是一个耗时的过程。资源消耗大：大量的计算意味着更多的CPU时间和内存资源被占用。回溯法：回溯法是一种通过探索所有可能的候选解来找出所有解的算法。对于纯素数问题，回溯法可以从最高位开始，逐步构建可能的纯素数。在每一步中，都会检查当前构建的数字是否满足部分条件，如果满足，则继续向前试探（在末尾添加一位数），如果它不是素数，就放弃它，然后尝试下一个数。由于纯素数的特性，递归过程中可以利用这一特性进行剪枝，即当发现当前数字不满足纯素数条件时，无需继续向前试探，直接回溯，大大提高效率。5寻找纯素数对比枚举法，回溯法的优点有：效率较高：通过剪枝策略，回溯法能够避免无用的计算，从而提高效率。易于理解和实现：回溯法的递归特性使其逻辑结构清晰，易于理解和编程实现。3.解题思路如图11-15描绘的过程所示，采取一种系统性的方法来寻找连续素数序列，该方法通过逐步构建并验证数字序列的每一位来实现。6寻找纯素数为简化起见，只演示了3位数的寻找过程，具体步骤如下：首先，从最高位的单个数字开始探索，试探2到9，其中2、3、5、7是素数，被保留下来，因为它们有潜力成为更长素数序列的起点。而4、6、8、9不是素数（图中在相应数字后打了叉），因此不基于它们继续试探，即实行剪枝。对于2、3、5、7四个起始素数，可以遵循一个过程：在其末尾逐一尝试添加新的数字（仅限奇数1、3、5、7、9，因为偶数不满足素数的条件）。7寻找纯素数4.代码实现boolisPrime(intn)

{

if

(n==

2)

return

true;

if

(n<=

1

||n%

2

==

0)

return

false;

for

(inti=

3;i*i<=n;i+=

2)

{

if

(n%i==

0)

return

false;

}

return

true;

}voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

9;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}intmain()

{

for

(inti=

2;i<=

9;i++)

{

if

(isPrime(i))

{

findPurePrimes(i,

1);

}

}

return

0;

}图11-15寻找纯素数的递归过程8寻找纯素数voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}从最高位开始试探，以2为例22123231num2len1newNum21i1323voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}num23len2newNumi12313233233voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}num233len3√9寻找纯素数voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}从最高位开始试探，以2为例num2len1newNumi323voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}num23len2newNumi3233522123231233√10寻找纯素数voidfindPurePrimes(intnum,

intlen)

{

if

(len==

3)

{

cout<<num<<endl;

return;

}

for

(inti=

1;i<=

3;i+=

2)

{

intnewNum=num*

10

+i;

if

(isPrime(newNum))

{

findPurePrimes(newNum,len+

1);

}

}

}从最高位开始试探，以2为例num2len1newNumi32322123231233√11全排列1.问题描述例：给定一个字符串，要求生成并输出该字符串中所有字符的全排列组合。以包含三个字母的字符串“abc”为例，其全排列集合包含六个不同的排列方式，具体为：abc,acb,bac,bca,cab,cba。该过程涉及到字符串的重新排列与组合，确保每个字符均能在结果集中以不同的顺序出现一次且仅一次，从而全面覆盖所有可能的排列情形。2.解题思路以字符串“abc”为例，采用回溯法实现全排列的过程可以描述如下（参照图11-16）：开始阶段：从字符串“abc”中选取第一个字符，有3种选择（a,b,c）。递归深入：每选定一个字符后，将其视为已处理并加入到当前排列中，递归地对剩余的字符进行同样的处理。终止条件：当没有剩余字符时，说明已经生成了一个完整的排列，此时将其记录下来或输出。回溯：在递归返回的过程中，撤销上一步的选择，以便尝试其他可能的选择。12全排列3.实现代码#include<iostream>#include<string>using

namespacestd;

voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}intmain()

{

stringstr;

cin>>str;

permute(str,

"");

return

0;

}图11-16求全排列递归过程13全排列3.实现代码voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strabcresi0aremainingbcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbcresai0abremainingcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strcresabi0abcremainingvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strresabcaababcbcc14全排列3.实现代码voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strabcresi0aremainingbcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbcresi0abremainingcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strcresi0abcremainingab1aababcbcc15全排列3.实现代码voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strabcresi0aremainingbcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbcresi0abremainingca1acbvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbresaci0acbremainingvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strresacbaababcbccacacbb16全排列3.实现代码voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strabcresi0aremainingbcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbcresiremaining1acbvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbresi0acbremainingac1aababcbccacacbb17全排列3.实现代码voidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strabcresi0aremainingbcvoidpermute(stringstr,stringres)

{

if

(str.empty())

{

cout<<res<<endl;

return;

}

for

(inti=

0;i<str.size();i++)

{

res.push_back(str[i]);

stringremaining=str.substr(0,i)

+str.substr(i+

1);

permute(remaining,res);

res.pop_back();

}

}strbcresiremaining1acba21baababcbccacacbb之后的过程和a类似，直到找到全排列所有值b18N皇后问题1.问题描述例：N皇后问题是一个经典的回溯算法问题。在这个问题中，你需要在一个N×N的棋盘上放置N个皇后，使得没有两个皇后在同一行、同一列或同一对角线上。2.解题思路（1）在第1行放置第一个皇后（2）在第2行放置第二个皇后（3）在第3行放置第三个皇后（4）将第2行的皇后放置到第4列，再尝试第3行、第4行，将发现没有符合条件的方案。（5）回溯到第1行，将第1个皇后放置到第2列6）如图11-17所示，在第2行第4列放置第2个皇后，第3行第1列放置第3个皇后，第4行第3列放置第4个皇后，得到一个有效的解决方案。19N皇后问题3.实现代码#defineN4intsolutions=

0;

intboard[N][N];

voidprintSolution(intboard[N][N])

{

for

(inti=

0;i<N;i++)

{

for

(intj=

0;j<N;j++)

printf("%d",board[i][j]);

printf("\n");

}

}boolisSafe(introw,

intcol)

{

for

(inti=

0;i<row;i++)

if

(board[i][col])

return

false;

for

(inti=row,j=col;i>=0

&&j>=0;i--,j--)

if

(board[i][j])

return

false;

for

(inti=row,j=col;i>=0

&&j<N;i--,j++)

if

(board[i][j])

return

false;

return

true;

}图11-17四皇后问题递归过程20N皇后问题3.实现代码boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}intmain()

{

solveNQUtil(0);

cout<<

"Totalsolutions:"

<<solutions<<endl;

return

0;

}21N皇后问题boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}当前位置安全：行、列、对角线都不存在皇后1boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}row++之后,row=1循环row行每一列，找到安全的位置，循环到i=2的时候位置才安全1boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}1boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}22N皇后问题boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}1boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}1boolsolveNQUtil(introw){

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for(inti=0;i<N;i++){if(isSafe(row,i)){board[row][i]=1;solveNQUtil(row+1);board[row][i]

=

0;

}

}

return

false;

}1N=3的情况下，其它列都找不到满足条件的情况了23N皇后问题boolsolveNQUtil(introw)

{

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for

(inti=

0;i<N;i++)

{

if

(isSafe(row,i))

{

board[row][i]

=

1;

solveNQUtil(row+

1);

board[row][i]

=

0;

}

}

return

false;

}1boolsolveNQUtil(introw){

if

(row==N)

{

solutions++;

printSolution(board);

cout<<

"\n";

return

false;

}

for(inti=0;i<N;i++){if(isSafe(row,i)){board[row][i]=1;solveNQUtil(row+1);board[row][i]

=

0;

}

}

return

false;

}124N皇后问题3.实现代码—分析（1）solveNQUtil函数中为什么要将board[row][i]赋值为0？board[row][i]表示棋盘上的一个位置，其中row是行号，i是列号。board[row][i]=1;表示在棋盘的第row行第i列放置一个皇后。board[row][i]=0;则表示从棋盘的第row行第i列移除皇后。将board[row][i]赋值为0是回溯算法的典型步骤。首先，尝试在某个位置放置皇后，然后递归地尝试放置其他皇后。从深层次递归返回后，再撤销刚才的选择，并尝试下一个可能的选择。这就是所谓的“回溯”。25N皇后问题3.实现代码—分析（2）isSafe函数的代码如何理解？这段代码中的三个for循环都用来检查在棋盘的(row,col)位置放置一个皇后是否安全。因为所有之前放置的皇后都在当前皇后的上方，所以，以下三个循环只检查上方是否已有皇后，而不检查下方。第一个for循环功能为：检查当前列上是否已经有皇后。如果在(row,col)位置上方的任何位置有皇后（即board[i][col]为1），那么在(row,col)位置放置皇后就不安全，返回false。第二个for循环功能为：检查当前位置的左上对角线上是否已经有皇后。如果在(row,col)位置的左上对角线上的任何位置有皇后（即board[i][j]为1），那么在(row,col)位置放置皇后就不安全，返回false。第三个for循环功能为：检查当前位置的右上对角线上是否已经有皇后。如果在(row,col)位置的右上对角线上的任何位置有皇后（即board[i][j]为1），那么在(row,col)位置放置皇后就不安全，返回false。2递归算法：分治法27二分查找例：二分查找是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且使用同样的方法查找。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。步骤：（1）分解：将当前问题分解为两个子问题。（2）解决：使用递归方法解决子问题。如果子问题足够小，则直接解决。（3）合并：在二分查找中，实际上并不需要合并步骤，因为我们只需要找到目标值即可。28二分查找代码实现：intbinarySearchRecursive(intarr[],

intleft,

intright,

intx)

{

if

(right>=left)

{

intmid=left+

(right-left)

/

2;

if

(arr[mid]

==x)

returnmid;

if

(arr[mid]

>x)

returnbinarySearchRecursive(arr,left,mid-

1,x);

returnbinarySearchRecursive(arr,mid+

1,right,x);

}

return

-1;

}29二分查找代码实现：intmain()

{

intarr[10]

=

{2,

3,

4,

10,

40,

50,

60,

70,

80,

90};

intx=

3;

intresult=binarySearchRecursive(arr,

0,

9,x);

if

(result==

-1)

cout<<

"未找到"

<<

endl;

else

cout<<

"下标："

<<

result<<endl;

return

0;

}30二分查找intbinarySearchRecursive(intarr[],

intleft,

intright,

intx)

{

if

(right>=left)

{

intmid=left+

(right-left)

/

2;

if

(arr[mid]

==x)

returnmid;

if

(arr[mid]

>x)

returnbinarySearchRecursive(arr,left,mid-

1,x);

returnbinarySearchRecursive(arr,mid+

1,right,x);

}

return

-1;

}23410405060708090leftrightmid31二分查找intbinarySearchRecursive(intarr[],

intleft,

intright,

intx)

{

if

(right>=left)

{

intmid=left+

(right-left)

/

2;

if

(arr[mid]

==x)

returnmid;

if

(arr[mid]

>x)

returnbinarySearchRecursive(arr,left,mid-

1,x);

returnbinarySearchRecursive(arr,mid+

1,right,x);

}

return

-1;

}23410405060708090leftrightmid32归并排序例：归并排序是一种采用分治法的排序算法。它将待排序的元素序列分成两个长度相等（或相差1）的子序列，分别对这两个子序列递归地应用归并排序，然后将排序后的两个子序列合并成一个有序序列。步骤：（1）分解：将当前问题分解为两个子问题。（2）解决：使用递归方法解决子问题。如果子问题足够小（子数组的长度为1），则直接解决。（3）合并：将排序后的两个子数组合并为一个有序数组。33归并排序代码实现：#include<iostream>#include<vector>using

namespacestd;

vector<int>merge(vector<int>&left,vector<int>&right)

{

vector<int>result;

inti=

0,j=

0;

while(i<left.size()

&&j<right.size())

{

if(left[i]

<=right[j])

{

result.push_back(left[i]);i++;

}

else

{

result.push_back(right[j]);j++;

}

}

while(i<left.size())

{

result.push_back(left[i]);i++;

}

while(j<right.size())

{

result.push_back(right[j]);j++;

}

returnresult;

}34归并排序代码实现：vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}intmain()

{

vector<int>arr=

{5,3,8,7,1,4,9,2};

vector<int>sortedArr=mergeSort(arr);

for(inti:sortedArr)

{

cout<<i<<

"";

}

cout<<endl;

return

0;

}35归并排序vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}53871492midvector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}5387mid36归并排序vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}53871492midvector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}5387mid53mid37归并排序vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}5387mid53mid5vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}338归并排序vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}5387mid53mid5vector<int>mergeSort(vector<int>&arr)

{

if

(arr.size()

<=

1)

returnarr;

intmid=arr.size()

/

2;

vector<int>left(arr.begin(),arr.begin()

+mid);

vector<int>right(arr.begin()

+mid,arr.end());

left=mergeSort(left);

right=mergeSort(right);

returnmerge(left,right);

}339归并排序实现方法：（1）检查基本情况：如果arr的大小小于或等于1，那么它已经是排序的，所以直接返回arr。（2）分解：计算arr的中间索引mid，然后将arr分解为两个子向量left和right。left包含arr的前半部分，right包含arr的后半部分。（3）递归解决：对left和right子向量递归调用mergeSort函数。这将对left和right进行排序。（4）合并：最后，调用merge函数将排序后的left和right子向量合并为一个排序的向量，并返回这个向量。40归并排序递归过程：（1）分解阶段首先，将数组{5,