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;
}