C++ 将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;
}