面试算法：波浪型数组的快速排序法

波浪型数组是具备这样特性的数组，它的元素先是递增，到达某个点后开始低贱，接着达到某个点时又递增，接着右递减，以下数组就是一个波浪型数组：

A: 57, 131, 493, 294, 221, 339, 418, 452, 442, 190
A[0] A[1] A[2] A[3] A[4] A[5] A[6], A[7], A[8], A[9]

不难发现，A[0]-A[4]是一个波浪，因为它经历了递增然后递减的过程，同理A[5]-A[9]又是一个波浪。所以这个数组有两个波浪。

假设给定一个含有k个波浪的数组，要求设计一个高效算法对其进行排序，你可以申请一个同等大小的空数组，并且允许你再申请O(k)大小的额外空间。

首先我们先对每个波浪进行排序，从给定例子的第一个波浪，由于它具备先增后减的特性，于是我们可以在波浪的开头和末尾个放置一个指针，然后比对两个指针指向元素的大小，把较小的一个元素放入到另一个数组的相应位置，然后改变相应指针的位置，例如对于第一个波浪：

57(p1)， 131， 493， 294， 221(p2)

我们用P1指向第一个元素，用P2指向最后一个元素，然后比较两者大小，用于p1指向的值小于p2指向的值，所以把p1的值放入另一个数组相应的位置，然后前进p1的位置：
A: 57， 131(p1), 493, 294, 221(p2)
A1: 57
根据这个流程走完后，一个波浪中的元素就可以被排序了：
A: 57, 131, 493(p1,p2), 294, 221
A1: 57, 131, 221, 294, 493

我们先把每个波浪都排序，相关算法的实现代码如下：

public class WaveArraySorter {
    int[] waveArray = null;
    int[] orignalArray = null;
    int waveBegin = 0;
    int waveEnd = 0;

    public WaveArraySorter(int[] array) {
        waveArray = new int[array.length];
        this.orignalArray = array;
        findWaveAndSort();
    }

    private void findWaveAndSort() {
        int i = waveBegin = 0;
        boolean waveDown = false;
        while (i < orignalArray.length - 1) {
            if (orignalArray[i] > orignalArray[i+1]) {
                waveDown = true;    
            }

            boolean risingAgain = orignalArray[i] < orignalArray[i+1];
            boolean reachingEnd = (i + 1 == orignalArray.length - 1);

            if (waveDown == true && (risingAgain || reachingEnd)) {
                if (reachingEnd) {
                    waveEnd = i + 1;
                } else {
                    waveEnd = i;    
                }

                sortWave();
                waveBegin = i + 1;
                waveDown = false;
            }

            i++;
        }
    }

    private void sortWave() {
        int p = waveBegin;
        int begin = waveBegin;
        int end = waveEnd;
        while (begin <= end) {
            if (orignalArray[begin] <= orignalArray[end]) {
                waveArray[p] = orignalArray[begin];
                begin++;
            } else {
                waveArray[p] = orignalArray[end];
                end--;
            }

            p++;
        }
    }

}

不难看出，对每个波浪进行排序时，只要遍历一遍波浪中的元素就可以了，所以对所有波浪进行排序，所需的时间复杂度是O(n)。

上面代码运行后，波浪数组的每个波浪都会得到排序，根据上面例子，代码执行后，数组情况如下：

A1: 57, 131, 221, 294, 493, 190 , 339, 418, 442, 452

接下来要做的是，从每个波浪中取出最大值用来组成一个大堆，利用extract-maximun()从堆中获得最大值，把这个最大值放入到数组的末尾，假设这个最大值来自k个波浪中的第 t 个，那么我们从第t个波浪中取得它倒数第二大的值加入大堆，然后通过继续调用extract-maximun()获得最大值，这个最大值则是整个数组倒数第二大的值，以此类推我们就可以把整个波浪数组进行排序了。

假定给定一个波浪数组如下：
A: 57, 131, 493, 294, 221, 339, 418, 452, 442, 190, 230, 310, 510, 432, 271, 280, 350, 631, 450, 332

对每个波浪进行排序后，情况如下：

57, 131, 221, 294, 493 || 190, 339, 418, 442, 452 ||230, 271, 310, 432, 510 || 280, 332, 350, 450, 631

取出每个波浪的最大值组成一个大堆后情况如下：

heap: 631, 510, 452, 493

执行一次extract-maximun() 得到631， 由于它来自最后一个波浪，因此把631前面的450加入大堆：

heap: 510, 493, 452, 450

再次执行extract-maximun() 得到510，然后把510前面的值432加入大堆：

heap: 493, 452, 450, 432

继续执行extract-maximun()得到的值就是493，以此类推我们就可以把整个数组进行排序了。

如果数组有k个波浪，那么构造大堆的复杂度就是O(k* lgk)，extract-maximun的复杂度是O(1), 把元素加入一个含有k个元素的大堆，时间复杂度是O(lgk), 我们总共需要将n-k个元素加入大堆，因此总时间复杂度是O(n*lgk).

为了实现上面算法，我们定义下面数据结构：

public class Pair {
    public int val;
    public int begin;
    int end;

    public Pair(int v, int b, int e) {
        this.val = v;
        this.begin = b;
        this.end = e;
    }

    public void exchange(Pair pair) {
        int v = val;
        int b = begin;
        int e = end;

        this.val = pair.val;
        this.begin = pair.begin;
        this.end = pair.end;

        pair.val = v;
        pair.begin = b;
        pair.end = e;
    }
}

其中，exchange用来交换两个Pair对象的内容。

堆排序时，要对Pair中的val来排序，extract-maximun时，返回的对象不再是int,而是Pair。对上节堆排序代码的对应修改在这里就不罗列出来，具体内容可以查看视频。

我们再看看最后排序算法的具体实现：

private void findWaveAndSort() {
        int i = waveBegin = 0;
        boolean waveDown = false;
        while (i < orignalArray.length - 1) {
            if (orignalArray[i] > orignalArray[i+1]) {
                waveDown = true;    
            }

            boolean risingAgain = orignalArray[i] < orignalArray[i+1];
            boolean reachingEnd = (i + 1 == orignalArray.length - 1);

            if (waveDown == true && (risingAgain || reachingEnd)) {
                if (reachingEnd) {
                    waveEnd = i + 1;
                } else {
                    waveEnd = i;    
                }

                sortWave();

                Pair pair = new Pair(waveArray[waveEnd], waveBegin, waveEnd);
                pairArray.add(pair);

                waveBegin = i + 1;
                waveDown = false;
            }

            i++;
        }
    }

我们对每个波浪排序时，用Pair对象记录下波浪最后一个元素的值，以及波浪的起始和末尾位置。如果数组由k个波浪，那么我们会申请k个Pair对象。接着我们看看排序的实现：

public void sortArray() {
        Pair[] array = new Pair[pairArray.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = pairArray.get(i);
        }

        HeapPairSort hp = new HeapPairSort(array);
        hp.buildMaxHeap();

        int count = orignalArray.length - 1;
        while (count >= 0) {
            orignalArray[count] = max.val;
            if (max.end > max.begin) {
                max.end--;
                max.val = waveArray[max.end];
                hp.insert(max);
            } 
            count--;
        }
    }

sortWave 把每个波浪中的最大值集合在一起形成一个大堆，通过extract-maximun()得到大堆的最大元素，并把它放入到数组的合适位置，然后再把该最大元素的前一个元素加入到大堆中，该函数所实现的就是我们前面所说的堆排序算法。

完成以上代码后，在入口处我们添加如下代码：

int[] wave = new int[] {57, 131, 493, 294, 221,  339,  418, 452,  442, 190, 230, 310, 510, 432, 271, 
               280, 350, 631, 450, 332};
       WaveArraySorter was = new WaveArraySorter(wave);
       was.sortArray();
       for (int i = 0; i < wave.length; i++) {
           System.out.print(wave[i] + " ");
       }

我们先构造一个波浪形数组，然后使用sortArray对其排序，得到的最终结果为：
57 131 190 221 230 271 280 294 310 332 339 350 418 432 442 450 452 493 510 631

由此可见，数组被正确排序了，我们代码对算法的实现是正确的，更详实的讲解和代码调试演示过程，请参看视频：
如何进入google,算法面试技能全面提升指南

更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：