# 將數組轉換為 Zig-Zag 風格 > 原文： [https://www.geeksforgeeks.org/convert-array-into-zig-zag-fashion/](https://www.geeksforgeeks.org/convert-array-into-zig-zag-fashion/) 給定不同元素的數組，請在`O(n)`時間內以 Z 字形方式重新排列該數組的元素。 轉換后的數組應為`a < b > c < d > e < f`的形式。 **示例**： > **輸入**：`arr [] = {4, 3, 7, 8, , 2, 1}` > > **輸出**：`arr [] = {3, 7, 4, 8 , 2, 6, 1}` > > **輸入**：`arr [] = {1, 4, 3, 2}` > > **輸出**：`arr [] = {1, 4, 2, 3}` **簡單解決方案**是首先對數組進行排序。 排序后，排除第一個元素，成對交換其余元素。 （即，保持`arr[0]`不變，交換`arr[1]`和`arr[2]`，交換`arr[3]`和`arr[4]`，依此類推）。 **時間復雜度**：`O(N log N)`，因為我們需要首先對數組進行排序。 我們可以使用**有效方法**轉換為`O(n)`時間。 這個想法是使用經過修改的一遍冒泡排序。 * 維護一個用于表示當前需要哪個順序（即`<`或`>`）的標志。 * 如果當前的兩個元素不按該順序排列，則交換這些元素，否則不進行交換。 讓我們看一下使用三個連續元素 A，B，C 的主要邏輯。 假設我們當前正在處理 B 和 C，當前關系為`<`，但是`B > C`。由于當前關系為`<`，之前的關系必須是 A 大于 B。因此，該關系為`A > B`和`B > C`。 推導出`A > C`。因此，如果我們交換 B 和 C，則關系為`A > C`和`C < B`。最后我們得到所需的順序`A > C < B` 有關更多說明，[請參見這里](http://geeksquiz.com/converting-an-array-of-integers-into-zig-zag-fashion/)。 下圖是上述方法的模擬：  下面是上述方法的實現： ## C++ ```cpp // C++ program to sort an array in Zig-Zag form #include <iostream> using namespace std; // Program for zig-zag conversion of array void zigZag(int arr[], int n) { ????// Flag true indicates relation "<" is expected, ????// else ">" is expected.? The first expected relation ????// is "<" ????bool flag = true; ????for (int i=0; i<=n-2; i++) ????{ ????????if (flag)? /* "<" relation expected */ ????????{ ????????????/* If we have a situation like A > B > C, ???????????????we get A > B < C by swapping B and C */ ????????????if (arr[i] > arr[i+1]) ????????????????swap(arr[i], arr[i+1]); ????????} ????????else /* ">" relation expected */ ????????{ ????????????/* If we have a situation like A < B < C, ???????????????we get A < C > B by swapping B and C */ ????????????if (arr[i] < arr[i+1]) ????????????????swap(arr[i], arr[i+1]); ????????} ????????flag = !flag; /* flip flag */ ????} } // Driver program int main() { ????int? arr[] = {4, 3, 7, 8, 6, 2, 1}; ????int n = sizeof(arr)/sizeof(arr[0]); ????zigZag(arr, n); ????for (int i=0; i<n; i++) ????????cout << arr[i] << "? "; ????return 0; } ``` ## Java ```java // Java program to sort an array in Zig-Zag form import java.util.Arrays; class Test { ????static int arr[] = new int[]{4, 3, 7, 8, 6, 2, 1}; ????// Method for zig-zag conversion of array ????static void zigZag() ????{ ????????// Flag true indicates relation "<" is expected, ????????// else ">" is expected.? The first expected relation ????????// is "<" ????????boolean flag = true; ????????int temp =0; ????????for (int i=0; i<=arr.length-2; i++) ????????{ ????????????if (flag)? /* "<" relation expected */ ????????????{ ????????????????/* If we have a situation like A > B > C, ???????????????????we get A > B < C by swapping B and C */ ????????????????if (arr[i] > arr[i+1]) ????????????????{ ????????????????????// swap ????????????????????temp? = arr[i]; ????????????????????arr[i] = arr[i+1]; ????????????????????arr[i+1] = temp; ????????????????} ????????????} ????????????else /* ">" relation expected */ ????????????{ ????????????????/* If we have a situation like A < B < C, ???????????????????we get A < C > B by swapping B and C */ ????????????????if (arr[i] < arr[i+1]) ????????????????{ ????????????????????// swap ????????????????????temp = arr[i]; ????????????????????arr[i] = arr[i+1]; ????????????????????arr[i+1] = temp; ????????????????} ????????????} ????????????flag = !flag; /* flip flag */ ????????} ????} ????// Driver method to test the above function ????public static void main(String[] args)? ????{ ????????zigZag(); ????????System.out.println(Arrays.toString(arr)); ????} } ``` ## Python ``` # Python program to sort an array in Zig-Zag form # Program for zig-zag conversion of array def zigZag(arr, n): ????# Flag true indicates relation "<" is expected, ????# else ">" is expected.? The first expected relation ????# is "<" ????flag = True ????for i in range(n-1): ????????# "<" relation expected ????????if flag is True: ????????????# If we have a situation like A > B > C, ????????????#?? we get A > B < C? ????????????# by swapping B and C ????????????if arr[i] > arr[i+1]: ????????????????arr[i],arr[i+1] = arr[i+1],arr[i] ????????????# ">" relation expected ????????else: ????????????# If we have a situation like A < B < C, ????????????#?? we get A < C > B ????????????# by swapping B and C???? ????????????if arr[i] < arr[i+1]: ????????????????arr[i],arr[i+1] = arr[i+1],arr[i] ????????flag = bool(1 - flag) ????print(arr) # Driver program arr = [4, 3, 7, 8, 6, 2, 1] n = len(arr) zigZag(arr, n) # This code is contributed by Pratik Chhajer ``` Output: ``` 3 7 4 8 2 6 1 ``` **時間復雜度**：`O(n)` **輔助空間**： `O(1)`