# 重新排列數組，使偶數索引元素較小而奇數索引元素較大 > 原文： [https://www.geeksforgeeks.org/rearrange-array-even-index-elements-smaller-odd-index-elements-greater/](https://www.geeksforgeeks.org/rearrange-array-even-index-elements-smaller-odd-index-elements-greater/) 給定一個數組，重新排列數組，使得： 1. 如果索引`i`為偶數，則`arr[i] <= arr[i + 1]` 2. 如果索引`i`為奇數，則`arr[i] >= arr[i + 1]` **注意**：可以有多個答案。 **示例**： ``` Input : arr[] = {2, 3, 4, 5} Output : arr[] = {2, 4, 3, 5} Explanation : Elements at even indexes are smaller and elements at odd indexes are greater than their next elements Note : Another valid answer is arr[] = {3, 4, 2, 5} Input :arr[] = {6, 4, 2, 1, 8, 3} Output :arr[] = {4, 6, 1, 8, 2, 3} ``` 此問題類似于[以波形](https://www.geeksforgeeks.org/sort-array-wave-form-2/)對數組進行排序。 **簡單解決方案**是按降序對數組進行排序，然后從第二個元素開始，交換相鄰元素。 一種有效的**解決方案**是根據給定條件遍歷數組并交換元素。如果我們有一個長度為 n 的數組，那么我們將從索引 0 迭代到`n-2`并檢查給定條件。在任何時間點，如果`i`為偶數且`arr[i] > arr[i + 1]`，則我們交換`arr[i]`和`arr[i + 1]`。 類似地，如果`i`為奇數并且`arr[i] < arr[i + 1]`，則我們交換`arr[i]`和`arr[i + 1]`。 對于給定的示例：重排之前，`arr[] = {2, 3, 4, 5}`，開始遍歷數組直到索引 2（`n = 4`） > **第一步**： > 在`i = 0`時，`arr[i] = 2`且`arr [i + 1] = 3`。當`i`為偶數且`arr[i] < arr[i + 1]`時，無需交換。 > **第二步**： > 在`i = 1`時，`arr[i] = 3`且`arr[i + 1] = 4`。由于`i`為奇數且`arr[i] < arr[i + 1]`，將它們交換。 > 現在`arr [] = {2, 4, 3, 5}` > **第三步**： > 在`i = 2`時，`arr[i] = 3`且`arr[i + 1] = 5`。因此，無需交換它們 重新排列后，`arr[] = {2, 4, 3, 5}` ## C++ ```cpp // CPP code to rearrange an array such that // even index elements are smaller and odd // index elements are greater than their // next. #include <iostream> using namespace std; void rearrange(int* arr, int n) { ????for (int i = 0; i < n - 1; i++) { ????????if (i % 2 == 0 && arr[i] > arr[i + 1]) ????????????swap(arr[i], arr[i + 1]); ????????if (i % 2 != 0 && arr[i] < arr[i + 1]) ????????????swap(arr[i], arr[i + 1]); ????} } /* Utility that prints out an array in ???a line */ void printArray(int arr[], int size) { ????for (int i = 0; i < size; i++) ????????cout << arr[i] << " "; ????cout << endl; } /* Driver function to test above functions */ int main() { ????int arr[] = { 6, 4, 2, 1, 8, 3 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << "Before rearranging: \n"; ????printArray(arr, n); ????rearrange(arr, n); ????cout << "After rearranging: \n"; ????printArray(arr, n); ????return 0; } ``` ## Java ```java // Java code to rearrange an array such // that even index elements are smaller // and odd index elements are greater // than their next. class GFG { ????static void rearrange(int arr[], int n) ????{ ????????int temp; ????????for (int i = 0; i < n - 1; i++) { ????????????if (i % 2 == 0 && arr[i] > arr[i + 1]) { ????????????????temp = arr[i]; ????????????????arr[i] = arr[i + 1]; ????????????????arr[i + 1] = temp; ????????????} ????????????if (i % 2 != 0 && arr[i] < arr[i + 1]) { ????????????????temp = arr[i]; ????????????????arr[i] = arr[i + 1]; ????????????????arr[i + 1] = temp; ????????????} ????????} ????} ????/* Utility that prints out an array in ????a line */ ????static void printArray(int arr[], int size) ????{ ????????for (int i = 0; i < size; i++) ????????????System.out.print(arr[i] + " "); ????????System.out.println(); ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int arr[] = { 6, 4, 2, 1, 8, 3 }; ????????int n = arr.length; ????????System.out.print("Before rearranging: \n"); ????????printArray(arr, n); ????????rearrange(arr, n); ????????System.out.print("After rearranging: \n"); ????????printArray(arr, n); ????} } // This code is contributed by Anant Agarwal. ``` ## Python3 ```py # Python code to rearrange # an array such that # even index elements # are smaller and odd? # index elements are # greater than their? # next. def rearrange(arr, n): ????for i in range(n - 1): ????????if (i % 2 == 0 and arr[i] > arr[i + 1]): ????????????temp = arr[i] ????????????arr[i]= arr[i + 1] ????????????arr[i + 1]= temp ????????if (i % 2 != 0 and arr[i] < arr[i + 1]): ????????????temp = arr[i] ????????????arr[i]= arr[i + 1] ????????????arr[i + 1]= temp # Utility that prints out an array in # a line? def printArray(arr, size): ????for i in range(size): ????????print(arr[i], " ", end ="") ????print() # Driver code arr = [ 6, 4, 2, 1, 8, 3 ] n = len(arr) print("Before rearranging: ") printArray(arr, n) rearrange(arr, n) print("After rearranging:") printArray(arr, n); # This code is contributed # by Anant Agarwal. ``` ## C# ```cs // C# code to rearrange an array such // that even index elements are smaller // and odd index elements are greater // than their next. using System; class GFG { ????static void rearrange(int[] arr, int n) ????{ ????????int temp; ????????for (int i = 0; i < n - 1; i++) { ????????????if (i % 2 == 0 && arr[i] > arr[i + 1]) ????????????{ ????????????????temp = arr[i]; ????????????????arr[i] = arr[i + 1]; ????????????????arr[i + 1] = temp; ????????????} ????????????if (i % 2 != 0 && arr[i] < arr[i + 1]) ????????????{ ????????????????temp = arr[i]; ????????????????arr[i] = arr[i + 1]; ????????????????arr[i + 1] = temp; ????????????} ????????} ????} ????/* Utility that prints out an array in ????a line */ ????static void printArray(int[] arr, int size) ????{ ????????for (int i = 0; i < size; i++) ????????????Console.Write(arr[i] + " "); ????????Console.WriteLine(); ????} ????// Driver code ????public static void Main() ????{ ????????int[] arr = { 6, 4, 2, 1, 8, 3 }; ????????int n = arr.Length; ????????Console.WriteLine("Before rearranging: "); ????????printArray(arr, n); ????????rearrange(arr, n); ????????Console.WriteLine("After rearranging: "); ????????printArray(arr, n); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php? // PHP code to rearrange an array such? // that even index elements are smaller? // and odd index elements are greater? // than their next. function swap(&$a, &$b) { ????$temp = $a; ????$a = $b; ????$b = $temp; } function rearrange(&$arr, $n) { ????for ($i = 0; $i < $n - 1; $i++)? ????{ ????????if ($i % 2 == 0 &&? ????????????$arr[$i] > $arr[$i + 1]) ????????????swap($arr[$i], $arr[$i + 1]); ????????if ($i % 2 != 0 &&? ????????????$arr[$i] < $arr[$i + 1]) ????????????swap($arr[$i], $arr[$i + 1]); ????} } /* Utility that prints out? an array in a line */ function printArray(&$arr, $size) { ????for ($i = 0; $i < $size; $i++) ????????echo $arr[$i] . " "; ????echo "\n"; } // Driver Code $arr = array(6, 4, 2, 1, 8, 3 ); $n = sizeof($arr); echo "Before rearranging: \n"; printArray($arr, $n); rearrange($arr, $n); echo "After rearranging: \n"; printArray($arr, $n); // This code is contributed? // by ChitraNayal ?> ``` **輸出**： ``` Before rearranging: 6 4 2 1 8 3 After rearranging: 4 6 1 8 2 3 ``` **時間復雜度**： `O(n)` **參考**： [describe.codechef.com/questions/43062/anuund-editorial](http://discuss.codechef.com/questions/43062/anuund-editorial)