通过交换相邻元素对 1 到 N 进行排序

---

数组是一种线性数据结构，用于存储元素，而排序数组则按升序包含所有元素。通过交换相邻元素对数组进行排序意味着我们可以任意次数交换相邻元素，并且必须对数组进行排序。我们将得到两个数组，第一个数组是要排序的数组，另一个数组是布尔数组，表示当前元素是否可交换。

如果给定数组的长度为 N，则所有存在的元素都将是从 1 到 N。

输入

Given array:   1 2 4 3 5 7 6 
Boolean array: 0 1 1 1 0 1 1 

输出

Yes, we can sort the array. 

解释

我们可以交换 3 和 4，因为它们是可交换的，并且我们可以交换 6 和 7。

输入

Given array:   1 2 4 3 5 7 6 
Boolean array: 0 1 1 1 0 1 0 

输出

No, we cannot sort the array. 

解释

我们可以交换 3 和 4，因为它们是可交换的，但我们不能交换 6 和 7，这使得该数组未排序。

朴素方法

在这种方法中，我们将遍历数组，并将遍历布尔数组。如果当前索引是可交换的，那么我们将遍历到最后一个可交换索引，并使用排序函数对所有元素进行排序。最后，我们将检查数组是否已排序。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if the current array is sorted or not 
bool isSorted(int arr[], int n){    
   // traversing over the array 
   for(int i =1; i<n ;i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   // traversed over the whole array means sorted 
   return true;
}
// function to swap the elements of the array 
bool check(int arr[], bool brr[], int n){
	// traversing over the boolean array 
	for (int i = 0; i < n - 1; i++) {
		if (brr[i] == 1){
			int j = i;
			while (brr[j] == 1){
			   j++;
			}			
			// using sort function sort the array 
			sort(arr + i, arr + 1 + j);
			i = j; // updating the value of i
		}
	}

	return isSorted(arr, n);
}
int main(){
	int arr[] = { 1, 4, 2, 3, 5, 7, 6};
	bool brr[] = { 0, 1, 1, 1, 0, 1, 1 };
	int n = sizeof(arr) / sizeof(arr[0]); // getting the size of array    
	if(check(arr, brr, n)){
	   cout<<"Yes, the given array can be sorted"<<endl;
	}
	else{
	   cout<<"No, the given array cannot be sorted"<<endl;
	}    
   return 0;
}

输出

No, the given array cannot be sorted

时间和空间复杂度

上面代码的时间复杂度为 O(N*log(N))，其中 N 是给定数组的大小。

上面代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

方法 2

在这种方法中，我们将遍历给定数组，并检查当前元素是否不在其排序位置且不可交换，如果不可交换，则返回 false。否则，我们将获取当前点到下一个不可交换索引或数组末尾的所有可交换元素的数据。如果该范围内存在的元素少于或多于当前范围，我们将返回 false，否则在最后我们可以返回 true。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check the array can be sorted by swapping 
bool check(int arr[], bool brr[], int n){    
   int notAtPlace = 0; // variable to store elements that are not at place 
   int swappable = 0; // variable to store total elements that are swappable    
	// traversing over the Boolean array 
	for (int i = 0; i < n ; i++) {
	   if(arr[i] != (i+1) && brr[i] == 0) return false;	    
		if (brr[i] == 1 && arr[i] != i+1){
			int j = i;			
			//variable to get the maximum swappable value 
			// variable to get the minimum swappable value
			int mx = arr[i]-1;
			int mi = arr[i]-1;			
			while(j < n && brr[i] == 1){
			   mx = max(mx, arr[j]-1);
			   mi = min(mi, arr[j]-1);
			   j++;
			}
			if(mx > j || mi < i){
			   return false;
			}
			i = j-1;
		}
	}
   // traversed over the whole array means possible to sort
	return true;
}
int main(){
	int arr[] = { 1, 4, 2, 3, 5, 7, 6};
	bool brr[] = { 0, 1, 1, 1, 0, 1, 1 };
	int n = sizeof(arr) / sizeof(arr[0]); // getting the size of array     
	if(check(arr, brr, n)){
	   cout<<"Yes, the given array can be sorted"<<endl;
	}
	else{
	   cout<<"No, the given array cannot be sorted"<<endl;
	}    
   return 0;
}

输出

Yes, the given array can be sorted

时间和空间复杂度

上面代码的时间复杂度为 O(N)，其中 N 是给定数组的大小，因为我们只遍历数组一次。

上面代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，用于查找给定数组是否可以通过交换可交换的相邻元素进行排序。另一个数组将提供任何数组是否可交换。我们实现了两种方法，一种具有 O(N*log(N)) 时间和 O(1) 空间复杂度，而另一种具有相同空间复杂度，但时间复杂度提高到 O(N)。