[Algorithm]Reorder Array

Given an array with distinct elements a1, a2, a3...., reorder it as a1 < a2 > a3 < a4 >.......

对于这一题我们可以先分析array是sorted的话，我们的解法应该是什么样

• 如果array是偶数长度的话，我们只要从(a2，an-1）这一对开始每隔一对交换一对直到我们到达中间一对即可，这样可以的原因是比如我们交换a2这一对的时候换回来的值可以保证a1 < a2 > a3，对于a4那一对是一样的，注意只有长度为偶数的时候这个方法才work，是奇数的话中间总会三个是递增或者递减的，这是因为交换后中间元素的两边同时被交换的元素影响了。
• 如果array是奇数的话，我们把它转化成偶数即可，我们除掉第一个元素，剩下的元素是长度为偶数的数组，同时a1满足a1< a2（交换后的a2）的条件

所以，如果数组是sorted的话，我们用n / 2次交换就可以完成，如果数组不是sorted的话，我们进行n次交换也可以完成，具体的思想是如果A[k]和A[k+ 1]如果不满足他们应该有的关系，就交换，下面我们证明这样是可行的：

• 如果实际上A[k] < A[k + 1]，但他们的关系应该是A[k] > A[k + 1]。因为A[k]之前的部分是reordered的，我们可以得知A[k - 1] < A[k]，那么实际上A[k - 1] < A[k + 1]，那么交换A[k]，A[k + 1]后A[k - 1] < A[k] > A[k + 1]也成立
• 如果实际上A[k] > A[k + 1]，但他们的关系应该是A[k] < A[k + 1]。根据reorder的结果我们可以得知A[k - 1] >A[k]，那么实际上A[k - 1] > A[k + 1]，那么交换A[k]，A[k + 1]后A[k - 1] > A[k] < A[k + 1]也成立

代码如下：