波浪排序

发表于 本文字数： 1.5k 阅读时长 ≈ 5 分钟 分类于 标签：

偶然间看到了一道算法题，第一眼看起来还挺简单，但是想了想发现不止这么简单，应该会有更优解。拿“波浪排序”作为关键字在百度上进行搜索，发现并没有相关题目。又以“sort wave”为关键字在谷歌上进行搜索，终于发现了相关解析，这里用自己的方式记录一下解题思路。

首先来看题目：

将给定的数组中的元素进行波浪形排序，输出任意正确结果。
波浪形排序是指: arr[0] ≥ arr[1] ≤ arr[2] ≥ arr[3] ≤ arr[4] ≥ arr[5]
例如:
输入: 1, 2, 6, 7, 5, 3, 4
输出: 4, 1, 7, 5, 6, 2, 3

解法参考：Sort an array in a waveform

一、排序解法

排序解法是最简单也是最容易想到的解法。首先对数组进行排序，升序降序不重要，因为解法有很多种。

排序后我们可以：

  • 从两端分别拿取最大值和最小值，逐渐完成排序
  • 算出数组中间元素，则将整个数组划分为了小半区和大半区，然后同样分别往两端拿取各半区元素，完成排序
  • 升序排序后，偶数位（非数组下标位）的元素一定会大于等于前面的元素，将偶数位元素分别与前面的元素交换

因为第三种解法不需要额外的空间占用，所以我们主要关注第三种解法。

图解

把参考链接里面现成的图拿过来方便理解。

对原数组进行排序：

然后分别交换偶数位及前面的元素：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] sort(int[] arr) {

    Arrays.sort(arr);

    int tmp;

    for (int i = 1; i < arr.length; i = i + 2) {
        tmp = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = tmp;
    }

    return arr;
}

复杂度分析

排序后再遍历处理的时间复杂度为排序的时间复杂度 + 后续遍历处理时间复杂度，最优为：O(nlog⁡2n)O(n\log_2 n) + O(n)O(n) = O(nlog⁡2n)O(n\log_2 n)
空间复杂度仍然取决于使用的排序算法 + 后续处理是否需要占用空间，最优为：堆排 + 交换解法 = O(1)O(1)

二、一次遍历解决

这道题的最优解在于，我们能否不使用排序，仅使用一次遍历完成波浪排序。

从上面的结果可以看出，符合要求的答案，偶数位的元素，一定小于等于其前面和其后面的元素（对应题目要求的 arr[0] ≥ arr[1] ≤ arr[2]、arr[2] ≥ arr[3] ≤ arr[4]）。所以我们可以认为，对于每个偶数位元素，其一定是与相邻两个的元素比较中的最小值。那么我们就遍历偶数位元素，与其相邻元素为一组，将其交换为组内的最小值。然后我们可以看到，划分并遍历元素组的时候，遍历步长为 2，而元素为 3 个一组，所以奇数位元素会参与两次比较交换。
画了个图便于理解，数字是排序完的一个结果，看上去直观一点：

所以我们还需要解决的问题就是，当一次交换后，比如上图中的 30-10-50 排列好后，在以 20 为中心进行分组交换的时候，50 如果再次被交换后（假如此时值不是 20 而是 100，那么则需要交换 50 和 100），会不会破坏左边已经排列好的结构。这里就需要定义我们的交换策略。

对于每组 3 个元素，可能会有以下情况并分别进行处理：

  • 最左端为最小值：那么将最左端与中间进行交换，这样最左端相当于值变大了。而对于前一个元素组，其作为最右端的值，变大并不会影响现有结构
  • 中间的为最小值：不需要任何操作
  • 最右端为最小值：将最右端与中间进行交换，最左端未进行变更

可以看到，基于以上逻辑，重合元素再第二次参与比较时，要么不变，要么变大，均不会影响原有结构。所以基于这种策略，逐渐遍历数组即可。

最后再来看一下临界情况。

  • 如果数组长度为奇数，则正好可以完全分组
  • 如果数组长度为偶数，则最后会有一个元素未参与比较。再看回上面那张图，在已经排列好 30-10-50-20-70-30-80 的情况下
    • 假设最后的值为 15（即小于等于倒数第二位的值），则无需处理
    • 假设最后的值为 90（即大于倒数第二位的值），则直接进行交换。由于倒数第二位的元素为上一分组最右端元素，此种交换情况会将其变大，由于上面的逻辑，所以仍不会破坏原有结构

所以整体基于这种步长为 2 的遍历和上述交换逻辑，一次遍历就可以完成要求的波浪排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int[] sort(int[] arr) {

    if (arr.length < 2) {
        return arr;
    }

    int tmp;

    for (int i = 1; i < arr.length - 1; i = i + 2) {

        if (arr[i] > arr[i - 1]) {
            tmp = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = tmp;
        }

        if (arr[i] > arr[i + 1]) {
            tmp = arr[i + 1];
            arr[i + 1] = arr[i];
            arr[i] = tmp;
        }
    }

    // 最后的边界
    if (arr.length % 2 == 0 && arr[arr.length - 1] > arr[arr.length - 2]) {
        tmp = arr[arr.length - 2];
        arr[arr.length - 2] = arr[arr.length - 1];
        arr[arr.length - 1] = tmp;
    }

    return arr;
}

复杂度分析

最后再来看一眼复杂度：

  • 时间复杂度：只需遍历一次数组，O(n)O(n)
  • 空间复杂度：只需临时变量进行元素交换，O(1)O(1)