# 将数组转换为 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)`