可以单独排序以使用C ++进行排序的最大分区数

我们给定N个数字的数组，元素位于0和N-1范围内。元素未排序。目标是找到可以单独排序的数组的最大分区数量，然后可以将其串联起来以构成一个完整的长度为N的排序数组。

选择每个分区以使其中的元素未排序。对于介于0到N-1之间的N个数字，排序后的元素的索引等于该值。Arr [i] = i。

我们将通过将每个元素与到目前为止在其左侧找到的最大值进行比较来解决此问题。当到达最大值的正确位置时（maximum == i）。左侧的所有元素都较少，因此可以创建一个单独的分区。它右边的一切都更大。现在，对其余正确的元素执行相同的过程，并将它们划分为多个分区。

让我们通过示例来理解。

输入− Arr [] = {0,3,2,1,4,5}

输出-最大分区数-3

说明-从0开始，令max = 0 Arr [0]

在索引0和3之间。最大为3。当到达索引i = 3（maxx == i）时。所以第一个分区是[0,3,2,1]

对于索引4，最大值为4。索引i = 4（maxx == i）。所以第二个分区是[4]

对于索引5，最大值为5。索引i = 5（maxx == i）。所以第二个分区是[5]

总共3个分区[0,3,2,1] [4] [5]。排序每个并连接。

输入-Arr [] = {5,4,3,2,1,0}

输出-最大分区数-1

说明-从0开始，令max = 0 Arr [0]

在索引0和5之间。最大为5。当到达索引i = 5（maxx == i）时。所以只有分区是[5,4,3,2,1,0]

以下程序中使用的方法如下

list-paddingleft-2">

• 我们采用整数数组Num []初始化，其数字范围为0到N。

• 函数partitions（int arr []，int n）将一个数组及其长度作为参数，并返回可以单独排序以使整个数组排序的最大分区数。

• 初始分区计数为0。初始最大值在maxx中为arr [0]。

• 对于从最左边的元素开始的所有元素。查找是否大于maxx。

• 如果arr [i]> maxx为true。更新maxx。

• 如果当前的maxx和index相同。（maxx == i），那么直到i的所有元素都是一个分区的一部分。增量计数。

• 对右边的所有其他元素执行此操作，直到结束。

• 返回结果作为计数。

示例

#include <bits/stdc++++.h>
using namespace std;
int partitions(int arr[], int n){
   int count = 0;
   int maxx = arr[0];
   for (int i = 0; i < n; ++i) {
      if(arr[i] > maxx)
         maxx=arr[i];
      if (maxx == i)
         count++;
   }
   return count;
}
int main(){
   int Num[] = { 2,1,0,4,5,3 };
   int len = 6;
   cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

Maximum partitions that can be sorted: 18