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;
}
输出:
90 10 49 1 5 2 23
时间复杂度:O(n),其中 n 是输入数组的大小。遍历数组中偶数元素的循环运行 n/2 次,每次迭代需要常数时间。
空间复杂度:O(1),因为该算法在原地对输入数组进行排序,而不使用任何依赖于输入大小的其他数据结构。唯一使用的额外空间是用于存储交换操作期间临时变量的常量空间量。