【每日一题】- 2019-08-22 - 奇偶排序

[azl397985856]

给定一个数组排序，使得奇数位的值不大于相邻偶数位的值。

比如：

OESort([1,2,3,4,5,6]); // [ 4, 1, 5, 2, 6, 3 ]
OESort([1,2,3,4,5,6,7,8,9, 0]) // [ 5, 0, 6, 1, 7, 2, 8, 3, 9, 4 ]

注意： 答案是不唯一的

[linyouxun]

function OESort(nums) {
    var len = nums.length;
    nums.sort((i, i2) => i - i2);
    for(var i = 0; i < len - 1; i+=2) {
        var tmp = nums[i];
        nums[i] = nums[i + 1];
        nums[i + 1] = tmp; 
    }
    return nums
}

[azl397985856]

1. 先排序，然后插入。 最容易想到， 时间复杂度O(nlogn)

function OESort(list) {
    const res = [];
    let cnt = 0;

    list.sort((a, b) => a - b);

    for(let i = 1; i < list.length; i += 2) {
        cnt++;
        res[i] = list[(i / 2) >>> 0];
    }
    for(let i = 0; i < list.length; i += 2) {
        res[i] = list[cnt + (i / 2) >>> 0];
    }

    return res;
}

但是排序其实是没有必要的，于是有了下面的解法。

2. 比较相邻，如果不满足条件则交换 时间复杂度O(n)

function OESort(list) {
    function swap(l, i, j) {
      const t = l[i];
      l[i] = l[j];
      l[j] = t;
    }
    for (let i = 0; i < list.length; i += 2) {
      if (list[i] < list[i + 1]) {
        swap(list, i, i + 1);
      }
      if (i > 1 && list[i] < list[i - 1]) {
        swap(list, i, i - 1);
      }
    }

    return list;
  }