通過交換相鄰元素將 1 排序為 N · GeeksForGeeks 中文系列教程

# 通過交換相鄰元素將 1 排序為 N > 原文： [https://www.geeksforgeeks.org/sort-1-n-swapping-adjacent-elements/](https://www.geeksforgeeks.org/sort-1-n-swapping-adjacent-elements/) 給定一個數組 A，其大小為 N，由元素 1 到 N 組成。由 N-1 個元素組成的布爾數組 B 表示，如果 B [i]為 1，則可以將 A [i]與 A [i + 1]交換。找出是否可以通過交換元素對 A 進行排序。 **示例**： ``` Input : A[] = {1, 2, 5, 3, 4, 6} B[] = {0, 1, 1, 1, 0} Output : A can be sorted We can swap A[2] with A[3] and then A[3] with A[4]. Input : A[] = {2, 3, 1, 4, 5, 6} B[] = {0, 1, 1, 1, 1} Output : A can not be sorted We can not sort A by swapping elements as 1 can never be swapped with A[0]=2. ``` 在這里，我們只能將 A [i]與 A [i + 1]交換。因此要查找數組是否可以排序。使用布爾數組 B，我們可以對 B 的連續序列 1 進行數組排序。最后，我們可以檢查 A 是否排序。 ## C++ ```cpp // CPP program to test whether array // can be sorted by swapping adjacent // elements using boolean array #include <bits/stdc++.h> using namespace std; // Return true if array can be // sorted otherwise false bool sortedAfterSwap(int A[], bool B[], int n) { ????int i, j; ????// Check bool array B and sorts ????// elements for continuous sequence of 1 ????for (i = 0; i < n - 1; i++) { ????????if (B[i]) { ????????????j = i; ????????????while (B[j]) ????????????????j++; ????????????// Sort array A from i to j ????????????sort(A + i, A + 1 + j); ????????????i = j; ????????} ????} ????// Check if array is sorted or not ????for (i = 0; i < n; i++) { ????????if (A[i] != i + 1) ????????????return false; ????} ????return true; } // Driver program to test sortedAfterSwap() int main() { ????int A[] = { 1, 2, 5, 3, 4, 6 }; ????bool B[] = { 0, 1, 1, 1, 0 }; ????int n = sizeof(A) / sizeof(A[0]); ????if (sortedAfterSwap(A, B, n)) ????????cout << "A can be sorted\n"; ????else ????????cout << "A can not be sorted\n"; ????return 0; } ``` ## Java ```java import java.util.Arrays; // Java program to test whether an array // can be sorted by swapping adjacent // elements using boolean array class GFG { ????// Return true if array can be ????// sorted otherwise false ????static boolean sortedAfterSwap(int A[], ???????????????????????????????????boolean B[], int n) ????{ ????????int i, j; ????????// Check bool array B and sorts ????????// elements for continuous sequence of 1 ????????for (i = 0; i < n - 1; i++) { ????????????if (B[i]) { ????????????????j = i; ????????????????while (B[j]) { ????????????????????j++; ????????????????} ????????????????// Sort array A from i to j ????????????????Arrays.sort(A, i, 1 + j); ????????????????i = j; ????????????} ????????} ????????// Check if array is sorted or not ????????for (i = 0; i < n; i++) { ????????????if (A[i] != i + 1) { ????????????????return false; ????????????} ????????} ????????return true; ????} ????// Driver program to test sortedAfterSwap() ????public static void main(String[] args) ????{ ????????int A[] = { 1, 2, 5, 3, 4, 6 }; ????????boolean B[] = { false, true, true, true, false }; ????????int n = A.length; ????????if (sortedAfterSwap(A, B, n)) { ????????????System.out.println("A can be sorted"); ????????} ????????else { ????????????System.out.println("A can not be sorted"); ????????} ????} } ``` ## Python3 ```py # Python 3 program to test whether an array # can be sorted by swapping adjacent # elements using a boolean array # Return true if array can be # sorted otherwise false def sortedAfterSwap(A, B, n) : ????# Check bool array B and sorts ????# elements for continuous sequence of 1 ????for i in range(0, n - 1) : ????????if (B[i]== 1) : ????????????j = i ????????????while (B[j]== 1) : ????????????????j = j + 1 ????????????# Sort array A from i to j ????????????A = A[0:i] + sorted(A[i:j + 1]) + A[j + 1:] ????????????i = j ????# Check if array is sorted or not ????for i in range(0, n) : ????????if (A[i] != i + 1) : ????????????return False ????return True # Driver program to test sortedAfterSwap() A = [ 1, 2, 5, 3, 4, 6 ] B = [ 0, 1, 1, 1, 0 ] n = len(A) if (sortedAfterSwap(A, B, n)) : ????print("A can be sorted") else : ????print("A can not be sorted") # This code is contributed # by Nikita Tiwari. ``` ## C# ```cs // C# program to test whether array // can be sorted by swapping adjacent // elements using boolean array using System; class GFG { ????// Return true if array can be ????// sorted otherwise false ????static bool sortedAfterSwap(int[] A, ????????????????????????????????bool[] B, ????????????????????????????????int n) ????{ ????????int i, j; ????????// Check bool array B and sorts ????????// elements for continuous sequence of 1 ????????for (i = 0; i < n - 1; i++) { ????????????if (B[i]) { ????????????????j = i; ????????????????while (B[j]) { ????????????????????j++; ????????????????} ????????????????// Sort array A from i to j ????????????????Array.Sort(A, i, 1 + j); ????????????????i = j; ????????????} ????????} ????????// Check if array is sorted or not ????????for (i = 0; i < n; i++) { ????????????if (A[i] != i + 1) { ????????????????return false; ????????????} ????????} ????????return true; ????} ????// Driver Code ????public static void Main() ????{ ????????int[] A = { 1, 2, 5, 3, 4, 6 }; ????????bool[] B = { false, true, true, true, false }; ????????int n = A.Length; ????????if (sortedAfterSwap(A, B, n)) { ????????????Console.WriteLine("A can be sorted"); ????????} ????????else { ????????????Console.WriteLine("A can not be sorted"); ????????} ????} } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP program to test whether array // can be sorted by swapping adjacent // elements using boolean array // Return true if array can be // sorted otherwise false function sortedAfterSwap($A, $B, $n) { ????// Check bool array B and sorts ????// elements for continuous sequence of 1 ????for ($i = 0; $i < $n - 1; $i++)? ????{ ????????if ($B[$i])? ????????{ ????????????$j = $i; ????????????while ($B[$j]) ????????????????$j++; ????????????// Sort array A from i to j ????????????sort($A); ????????????$i = $j; ????????} ????} ????// Check if array is sorted or not ????for ($i = 0; $i < $n; $i++) ????{ ????????if ($A[$i] != $i + 1) ????????????return false; ????} ????return true; } ????// Driver Code ????$A = array(1, 2, 5, 3, 4, 6); ????$B = array(0, 1, 1, 1, 0); ????$n = count($A); ????if (sortedAfterSwap($A, $B, $n)) ????????echo "A can be sorted\n"; ????else ????????echo "A can not be sorted\n"; // This code is contributed by Sam007 ?> ``` **輸出**： ``` A can be sorted ``` **替代方法** 在這里，我們討論一種非常直觀的方法，該方法也為所有情況提供了`O(n)`時間的答案。這里的想法是，只要二進制數組具有 1，我們就檢查數組 A 中的索引是否具有 i + 1。如果它不包含 i + 1，我們只需將 a [i]與 a [i + 1]交換即可。原因是數組應該將 i + 1 存儲在索引 i 處。如果數組是可排序的，則唯一允許的操作是交換。因此，如果不滿足所需條件，我們只需交換。如果數組是可排序的，交換將使我們更接近正確答案。并且如預期的那樣，如果該數組不可排序，則交換將導致同一數組的另一個未排序版本。 ## C++ ``` // CPP program to test whether array // can be sorted by swapping adjacent // elements using boolean array #include <bits/stdc++.h> using namespace std; // Return true if array can be // sorted otherwise false bool sortedAfterSwap(int A[], bool B[], int n) { ????for (int i = 0; i < n - 1; i++) { ????????if (B[i]) { ????????????if (A[i] != i + 1) ????????????????swap(A[i], A[i + 1]); ????????} ????} ????// Check if array is sorted or not ????for (int i = 0; i < n; i++) { ????????if (A[i] != i + 1) ????????????return false; ????} ????return true; } // Driver program to test sortedAfterSwap() int main() { ????int A[] = { 1, 2, 5, 3, 4, 6 }; ????bool B[] = { 0, 1, 1, 1, 0 }; ????int n = sizeof(A) / sizeof(A[0]); ????if (sortedAfterSwap(A, B, n)) ????????cout << "A can be sorted\n"; ????else ????????cout << "A can not be sorted\n"; ????return 0; } ``` ## Java ```java // Java program to test whether an array // can be sorted by swapping adjacent // elements using boolean array class GFG { ????// Return true if array can be ????// sorted otherwise false ????static int sortedAfterSwap(int[] A,? ????????????????????????????int[] B, int n) ????{ ????????int t = 0; ????????for (int i = 0; i < n - 1; i++)? ????????{ ????????????if (B[i] != 0)? ????????????{ ????????????????if (A[i] != i + 1) ????????????????????t = A[i]; ????????????????????A[i] = A[i + 1]; ????????????????????A[i + 1] = t; ????????????} ????????} ????????// Check if array is sorted or not ????????for (int i = 0; i < n; i++) ????????{ ????????????if (A[i] != i + 1) ????????????????return 0; ????????} ????????return 1; ????} ????// Driver Code ????public static void main(String[] args) ????{ ????????int[] A = { 1, 2, 5, 3, 4, 6 }; ????????int[] B = { 0, 1, 1, 1, 0 }; ????????int n = A.length; ????????if (sortedAfterSwap(A, B, n) == 0) ????????????System.out.println("A can be sorted"); ????????else ????????????System.out.println("A can not be sorted"); ????} } // This code is contributed? // by Mukul Singh. ``` ## Python3 ```py # Python3 program to test whether array? # can be sorted by swapping adjacent? # elements using boolean array? # Return true if array can be? # sorted otherwise false? def sortedAfterSwap(A,B,n): ????for i in range(0,n-1): ????????if B[i]: ????????????if A[i]!=i+1: ????????????????A[i], A[i+1] = A[i+1], A[i] ????# Check if array is sorted or not ????for i in range(n): ????????if A[i]!=i+1: ????????????return False ????return True # Driver program if __name__=='__main__': ????A = [1, 2, 5, 3, 4, 6] ????B = [0, 1, 1, 1, 0] ????n =len(A) ????if (sortedAfterSwap(A, B, n)) : ????????print("A can be sorted")? ????else : ????????print("A can not be sorted")? # This code is contributed by? # Shrikant13 ``` ## C# ``` // C# program to test whether array // can be sorted by swapping adjacent // elements using boolean array using System; class GFG { ????// Return true if array can be ????// sorted otherwise false ????static int sortedAfterSwap(int[] A,? ???????????????????????????????int[] B, int n) ????{ ????????int t = 0; ????????for (int i = 0; i < n - 1; i++)? ????????{ ????????????if (B[i] != 0)? ????????????{ ????????????????if (A[i] != i + 1) ????????????????????t = A[i]; ????????????????????A[i] = A[i + 1]; ????????????????????A[i + 1] = t; ????????????} ????????} ????????// Check if array is sorted or not ????????for (int i = 0; i < n; i++) ????????{ ????????????if (A[i] != i + 1) ????????????????return 0; ????????} ????????return 1; ????} ????// Driver Code ????public static void Main() ????{ ????????int[] A = { 1, 2, 5, 3, 4, 6 }; ????????int[] B = { 0, 1, 1, 1, 0 }; ????????int n = A.Length; ????????if (sortedAfterSwap(A, B, n) == 0) ????????????Console.WriteLine("A can be sorted"); ????????else ????????????Console.WriteLine("A can not be sorted"); ????} } // This code is contributed? // by Akanksha Rai ``` ## PHP ```php <?php? // PHP program to test whether array // can be sorted by swapping adjacent // elements using boolean array // Return true if array can be // sorted otherwise false function sortedAfterSwap(&$A, &$B, $n) { ????for ($i = 0; $i < $n - 1; $i++)? ????{ ????????if ($B[$i])? ????????{ ????????????if ($A[$i] != $i + 1) ????????????{ ????????????????$t = $A[$i]; ????????????????$A[$i] = $A[$i + 1]; ????????????????$A[$i + 1] = $t; ????????????} ????????} ????} ????// Check if array is sorted or not ????for ($i = 0; $i < $n; $i++)? ????{ ????????if ($A[$i] != $i + 1) ????????????return false; ????} ????return true; } // Driver Code $A = array( 1, 2, 5, 3, 4, 6 ); $B = array( 0, 1, 1, 1, 0 ); $n = sizeof($A); if (sortedAfterSwap($A, $B, $n)) ????echo "A can be sorted\n"; else ????echo "A can not be sorted\n"; // This code is contributed by ita_c ?> ``` **輸出**： ``` A can be sorted ``` * * * * * *