C++程序将数组排成波浪形

给定一个无序的整数数组，将数组排成波浪形的形式。如果数组arr[0..n-1]排成如下形式，那么它就是波浪形数组： arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ….

举例：

输入：  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
输出： arr[] = {10, 5, 6, 2, 20, 3, 100, 80} 或者
                 {20, 5, 10, 2, 80, 6, 100, 3} 或者
                 其他任何排成波浪形的数组

输入：  arr[] = {20, 10, 8, 6, 4, 2}
输出： arr[] = {20, 8, 10, 4, 6, 2} 或者
                 {10, 8, 20, 2, 6, 4} 或者
                 其他任何排成波浪形的数组

输入：  arr[] = {2, 4, 6, 8, 10, 20}
输出： arr[] = {4, 2, 8, 6, 20, 10} 或者
                 其他任何排成波浪形的数组

输入：  arr[] = {3, 6, 5, 10, 7, 20}
输出： arr[] = {6, 3, 10, 5, 20, 7} 或者
                 其他任何排成波浪形的数组

一种 简单的解决方法 是使用排序。首先对输入数组进行排序，然后交换所有相邻的元素。

例如，让输入数组为{3，6，5，10，7，20}。排序后，我们得到{3，5，6，7，10，20}。交换相邻的元素后，我们得到{5，3，7，6，20，10}。

以下是此简单方法的实现。

// 一个使用排序函数将数组排序成波浪形的C++程序
# include<iostream>
# include<algorithm>
using namespace std;
 
// 交换两个数的方法
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
 
// 将arr[0..n-1]按波浪形排序，即，
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]..
void sortInWave(int arr[], int n)
{
    // 对输入数组进行排序
    sort(arr, arr+n);
 
    // 交换相邻的元素
    for (int i=0; i<n-1; i += 2)
        swap(&arr[i], &arr[i+1]);
}
 
// 主函数，用于测试上述功能
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;
}

输出：

2 1 10 5 49 23 90

上述解决方案的时间复杂度为O(nLogn)，如果使用类似于归并排序、堆排序等O(nLogn)的排序算法，则可以将其实现为O(n)时间的单次遍历算法。该算法的思想基于以下事实：如果我们确保所有偶数位置的元素（在索引0、2、4、..处）都大于其相邻的奇数元素，那么我们就不必担心奇数位置的元素。以下是简要步骤。

1）遍历输入数组的所有偶数位置，并执行以下操作。

….a）如果当前元素小于前面的奇数元素，请交换前面的元素和当前元素。

….b）如果当前元素小于后面的奇数元素，请交换后面的元素和当前元素。

以下是实现以上简单算法的代码。

// 一种时间复杂度为 O(n) 的程序对输入数组进行波浪排序
# include<iostream>
using namespace std;
 
// 交换两个数的常用方法。
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
 
// 这个函数以波浪形式将 arr[0..n-1] 排序。即，arr[0] >=
// arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] ....
void sortInWave(int arr[], int n)
{
    // 遍历所有偶数元素
    for (int i = 0; i < n; i+=2)
    {
        // 如果当前偶数元素比前一个小
        if (i>0 && arr[i-1] > arr[i] )
            swap(&arr[i], &arr[i-1]);
 
        // 如果当前偶数元素比后一个小
        if (i<n-1 && arr[i] < arr[i+1] )
            swap(&arr[i], &arr[i + 1]);
    }
}
 
// 测试上面的函数的主程序。
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;
}