Java 中的摇摆排序

给定一个包含 n 个整数的数组 arr[]。我们的任务是以这样的方式对数组进行排序，使其形成一个摆动序列。如果存在多个摆动序列，则打印其中任何一个。数组的摆动序列满足以下条件：

arr[0] <= arr[1] >= arr[2] <= arr[3] >= arr[4] <= arr[5] …

示例：1

输入

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}

输出 {1, 6, 2, 7, 3, 8, 4, 9, 5}

解释：提到的序列形成了一个摆动序列。其他有效序列是：{5, 9, 1, 6, 3, 8, 2, 7, 4}, {2, 8, 3, 5, 4, 6, 1, 9, 7}, {1, 9, 2, 8, 3, 7, 4, 5}, and { 1, 3, 2, 5, 4, 7, 6, 9, 8}

示例：2

输入

int arr[] = {8, 12, 10, 11, 9}

输出 {8, 12, 9, 11, 10}

解释：提到的序列形成了一个摆动序列。其他有效序列是：{9, 11, 10, 12, 8}, {10, 12, 9, 11, 8}, and {8, 12, 10, 11, 9}

例如：3

输入

int arr[] = {-1, 0, 1, -2, -5}

输出 {-1, 0, -2, 1, -5}

解释：提到的序列形成了一个摆动序列。其他有效序列是：{0, 1, -5, -1, -2}, {-5, 0, -2, 1, -1}, {-5, 1, -2, 0, -1}, and { -1, 1, -2, 0, -5}

方法：使用排序

当我们将较大的元素放在数组的奇数位置（即第一个、第三个、第五个位置等）时，而较小的元素放在偶数位置（即第 0 个、第 2 个、第 4 个位置等）时，就可以实现 arr[0] <= arr[1] >= arr[2] <= ar[3] >= arr[4] <= arr[5] ….. 这样的序列。现在任务是找出较小和较大的元素，这可以通过对元素进行排序来实现。排序后，左侧的元素是较小的元素，右侧的元素是较大的元素。现在，我们将使用两个指针，一个从排序后数组的最左侧开始，另一个指针从排序后数组的最右侧开始。通过循环，我们将递增和递减指针。在每次迭代中，我们将递增指向较小元素的指针一位，并递减指向较大元素的指针一位。

文件名： WiggleSort.java

输出

For the input Array: 
1 2 3 4 5 6 7 8 9 
The wiggle sequence is: 
1 9 2 8 3 7 4 6 5  
 
For the input Array: 
8 12 10 11 9 
The wiggle sequence is: 
8 12 9 11 10  
 
For the input Array: 
-1 0 1 -2 -5 
The wiggle sequence is: 
-5 1 -2 0 -1

复杂度分析：由于进行了排序，因此程序的时间复杂度为 O(n x log(n))。此外，程序使用 ArrayList 来存储结果，因此程序的空间复杂度为 O(n)，其中 n 是输入数组中存在的总元素数量。

如果我们仔细观察，就没有必要对数组进行排序。如果相邻的元素对不符合摆动序列，我们可以交换它们。这样，我们不仅避免了对输入数组进行排序，还避免了在之前的程序中使用额外的空间将结果存储在 ArrayList 中。下面的程序显示了这一点。

文件名： WiggleSort1.java

输出

For the input Array: 
1 2 3 4 5 6 7 8 9 
The wiggle sequence is: 
1 3 2 5 4 7 6 9 8  
 
For the input Array: 
8 12 10 11 9 
The wiggle sequence is: 
8 12 10 11 9  
 
For the input Array: 
-1 0 1 -2 -5 
The wiggle sequence is: 
-1 1 -2 0 -5

复杂度分析：由于程序使用了 for 循环，因此程序的时间复杂度为 O(n)，其中 n 是输入数组中存在的总元素数量。程序的空间复杂度是常数，即 O(1)。