[Google] Weird Sort Array

Question

link

数组排序， 排成 a1a3a5。。。这种形式。

Solution

The are 2 solutions. The easy one is this:

sort first, then 把临近的奇数换到偶数(index)上, O(nlog n).

There’s a great O(n) solution however, not easy to think:

两两比较相邻数字，把大的数字放到下标为奇数的位置。 O(n).

Code

O(nlgn) solution

public void solutionOnlgn(int[] A) {
    // this is a O(nlgn) solution
    Arrays.sort(A);
    for (int i = 2; i < A.length; i += 2) {
        swap(A, i - 1, i);
    }
}

private void swap(int[] A, int a, int b) {
    A[a] ^= A[b];
    A[b] ^= A[a];
    A[a] ^= A[b];
}

O(n) solution

public void solutionOn(int[] A) {
    // this is a O(n) solution
    for (int i = 1; i < A.length; i++) {
        // compare (i)th with (i-1)th, and put the large value
        // at odd-indexed positions
        if ((A[i - 1] < A[i] && i % 2 == 0)
                || (A[i - 1] > A[i] && i % 2 == 1)) {
            swap(A, i - 1, i);
        }
    }
}

private void swap(int[] A, int a, int b) {
    A[a] ^= A[b];
    A[b] ^= A[a];
    A[a] ^= A[b];
}