# 以波形形式對數組進行排序 > 原文： [https://www.geeksforgeeks.org/sort-array-wave-form-2/](https://www.geeksforgeeks.org/sort-array-wave-form-2/) 給定一個未排序的整數數組，將該數組排序為類似 wave 的數組。 如果 arr [0] > = arr [1] < = arr [2] > = arr [3] <，則數組'arr [0..n-1]'將以波形形式排序。 = arr [4] > =….. = > = > 例子： ``` Input: arr[] = {10, 5, 6, 3, 2, 20, 100, 80} Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR {20, 5, 10, 2, 80, 6, 100, 3} OR any other array that is in wave form Input: arr[] = {20, 10, 8, 6, 4, 2} Output: arr[] = {20, 8, 10, 4, 6, 2} OR {10, 8, 20, 2, 6, 4} OR any other array that is in wave form Input: arr[] = {2, 4, 6, 8, 10, 20} Output: arr[] = {4, 2, 8, 6, 20, 10} OR any other array that is in wave form Input: arr[] = {3, 6, 5, 10, 7, 20} Output: arr[] = {6, 3, 10, 5, 20, 7} OR any other array that is in wave form ``` **簡單解決方案**將使用排序。 首先對輸入數組進行排序，然后交換所有相鄰元素。 例如，讓輸入數組為{3，6，5，10，7，20}。 排序后，我們得到{3，5，6，7，10，20}。 交換相鄰元素后，我們得到{5，3，7，6，6，20，10}。 以下是此簡單方法的實現。 ## C++ ```cpp // A C++ program to sort an array in wave form using // a sorting function #include<iostream> #include<algorithm> using namespace std; // A utility method to swap two numbers. void swap(int *x, int *y) { ????int temp = *x; ????*x = *y; ????*y = temp; } // This function sorts arr[0..n-1] in wave form, i.e.,? // arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5].. void sortInWave(int arr[], int n) { ????// Sort the input array ????sort(arr, arr+n); ????// Swap adjacent elements ????for (int i=0; i<n-1; i += 2) ????????swap(&arr[i], &arr[i+1]); } // Driver program to test above function int main() { ????int arr[] = {10, 90, 49, 2, 1, 5, 23}; ????int n = sizeof(arr)/sizeof(arr[0]); ????sortInWave(arr, n); ????for (int i=0; i<n; i++) ???????cout << arr[i] << " "; ????return 0; } ``` ## Java ```java // Java implementation of naive method for sorting // an array in wave form. import java.util.*; class SortWave { ????// A utility method to swap two numbers. ????void swap(int arr[], int a, int b) ????{ ????????int temp = arr[a]; ????????arr[a] = arr[b]; ????????arr[b] = temp; ????} ????// This function sorts arr[0..n-1] in wave form, i.e., ????// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4].. ????void sortInWave(int arr[], int n) ????{ ????????// Sort the input array ????????Arrays.sort(arr); ????????// Swap adjacent elements ????????for (int i=0; i<n-1; i += 2) ????????????swap(arr, i, i+1); ????} ????// Driver method ????public static void main(String args[]) ????{ ????????SortWave ob = new SortWave(); ????????int arr[] = {10, 90, 49, 2, 1, 5, 23}; ????????int n = arr.length; ????????ob.sortInWave(arr, n); ????????for (int i : arr) ????????????System.out.print(i + " "); ????} } /*This code is contributed by Rajat Mishra*/ ``` ## Python ``` # Python function to sort the array arr[0..n-1] in wave form, # i.e., arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] def sortInWave(arr, n): ????#sort the array ????arr.sort() ????# Swap adjacent elements ????for i in range(0,n-1,2): ????????arr[i], arr[i+1] = arr[i+1], arr[i] # Driver progrM arr = [10, 90, 49, 2, 1, 5, 23] sortInWave(arr, len(arr)) for i in range(0,len(arr)): ????print arr[i], # This code is contributed by __Devesh Agrawal__ ``` ## C# ```cs // C# implementation of naive method? // for sorting an array in wave form. using System; class SortWave { ????// A utility method to swap two numbers. ????void swap(int[] arr, int a, int b) ????{ ????????int temp = arr[a]; ????????arr[a] = arr[b]; ????????arr[b] = temp; ????} ????// This function sorts arr[0..n-1] in wave form, i.e., ????// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4].. ????void sortInWave(int[] arr, int n) ????{ ????????// Sort the input array ????????Array.Sort(arr); ????????// Swap adjacent elements ????????for (int i = 0; i < n - 1; i += 2) ????????????swap(arr, i, i + 1); ????} ????// Driver method ????public static void Main() ????{ ????????SortWave ob = new SortWave(); ????????int[] arr = { 10, 90, 49, 2, 1, 5, 23 }; ????????int n = arr.Length; ????????ob.sortInWave(arr, n); ????????for (int i = 0; i < n; i++) ????????Console.Write(arr[i] + " "); ????} } // This code is contributed by vt_m. ``` Output: ``` 2 1 10 5 49 23 90 ``` 如果使用諸如[合并排序](http://geeksquiz.com/merge-sort/)，[堆排序](http://geeksquiz.com/heap-sort/)等的 O（nLogn）排序算法，則上述解決方案的時間復雜度為 O（nLogn）。 通過對給定數組進行單次遍歷，可以在 **`O(n)`時間內完成此操作。 這個想法基于這樣一個事實：如果我們確保所有偶數定位（在索引 0、2、4，..）的元素都大于其相鄰的奇數元素，則無需擔心奇數定位的元素。 以下是簡單的步驟。 1）遍歷輸入數組的所有偶數定位元素，然后執行以下操作。 ….a）如果當前元素小于前一個奇數元素，則交換前一個和當前元素。 ….b）如果當前元素小于下一個奇數元素，則交換 next 和 current。** 以下是上述簡單算法的實現。 ## C++ ``` // A O(n) program to sort an input array in wave form #include<iostream> using namespace std; // A utility method to swap two numbers. void swap(int *x, int *y) { ????int temp = *x; ????*x = *y; ????*y = temp; } // This function sorts arr[0..n-1] in wave form, i.e., arr[0] >=? // arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] .... void sortInWave(int arr[], int n) { ????// Traverse all even elements ????for (int i = 0; i < n; i+=2) ????{ ????????// If current even element is smaller than previous ????????if (i>0 && arr[i-1] > arr[i] ) ????????????swap(&arr[i], &arr[i-1]); ????????// If current even element is smaller than next ????????if (i<n-1 && arr[i] < arr[i+1] ) ????????????swap(&arr[i], &arr[i + 1]); ????} } // Driver program to test above function int main() { ????int arr[] = {10, 90, 49, 2, 1, 5, 23}; ????int n = sizeof(arr)/sizeof(arr[0]); ????sortInWave(arr, n); ????for (int i=0; i<n; i++) ???????cout << arr[i] << " "; ????return 0; } ``` ## Java ```java // A O(n) Java program to sort an input array in wave form class SortWave { ????// A utility method to swap two numbers. ????void swap(int arr[], int a, int b) ????{ ????????int temp = arr[a]; ????????arr[a] = arr[b]; ????????arr[b] = temp; ????} ????// This function sorts arr[0..n-1] in wave form, i.e., ????// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4].... ????void sortInWave(int arr[], int n) ????{ ????????// Traverse all even elements ????????for (int i = 0; i < n; i+=2) ????????{ ????????????// If current even element is smaller ????????????// than previous ????????????if (i>0 && arr[i-1] > arr[i] ) ????????????????swap(arr, i-1, i); ????????????// If current even element is smaller ????????????// than next ????????????if (i<n-1 && arr[i] < arr[i+1] ) ????????????????swap(arr, i, i + 1); ????????} ????} ????// Driver program to test above function ????public static void main(String args[]) ????{ ????????SortWave ob = new SortWave(); ????????int arr[] = {10, 90, 49, 2, 1, 5, 23}; ????????int n = arr.length; ????????ob.sortInWave(arr, n); ????????for (int i : arr) ????????????System.out.print(i+" "); ????} } /*This code is contributed by Rajat Mishra*/ ``` ## Python ``` # Python function to sort the array arr[0..n-1] in wave form, # i.e., arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] def sortInWave(arr, n): ????# Traverse all even elements ????for i in range(0, n, 2): ????????# If current even element is smaller than previous ????????if (i> 0 and arr[i] < arr[i-1]): ????????????arr[i],arr[i-1] = arr[i-1],arr[i] ????????# If current even element is smaller than next ????????if (i < n-1 and arr[i] < arr[i+1]): ????????????arr[i],arr[i+1] = arr[i+1],arr[i] # Driver program arr = [10, 90, 49, 2, 1, 5, 23] sortInWave(arr, len(arr)) for i in range(0,len(arr)): ????print arr[i], # This code is contributed by __Devesh Agrawal__ ``` ## C# ``` // A O(n) C# program to sort an // input array in wave form using System; class SortWave { ????// A utility method to swap two numbers. ????void swap(int[] arr, int a, int b) ????{ ????????int temp = arr[a]; ????????arr[a] = arr[b]; ????????arr[b] = temp; ????} ????// This function sorts arr[0..n-1] in wave form, i.e., ????// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4].... ????void sortInWave(int[] arr, int n) ????{ ????????// Traverse all even elements ????????for (int i = 0; i < n; i += 2) { ????????????// If current even element is smaller ????????????// than previous ????????????if (i > 0 && arr[i - 1] > arr[i]) ????????????????swap(arr, i - 1, i); ????????????// If current even element is smaller ????????????// than next ????????????if (i < n - 1 && arr[i] < arr[i + 1]) ????????????????swap(arr, i, i + 1); ????????} ????} ????// Driver program to test above function ????public static void Main() ????{ ????????SortWave ob = new SortWave(); ????????int[] arr = { 10, 90, 49, 2, 1, 5, 23 }; ????????int n = arr.Length; ????????ob.sortInWave(arr, n); ????????for (int i = 0; i < n; i++) ????????Console.Write(arr[i] + " "); ????} } // This code is contributed by vt_m. ``` 輸出： ``` 90 10 49 1 5 2 23 ```