将整数数组排序为奇数,然后是偶数

Question

我在其他地方的算法论坛上发现了一个问题.

我有一个随机数的数组(例如[5, 2, 7, 9, 2, 3, 8, 4]),应该返回给我,按奇数排序然后偶数.赔率/均匀的顺序并不重要,所以在这个例子中可能是这样[5, 7, 9, 3, 2, 2, 8, 4].

我的第一个想法是使用一个.reduce()函数将它们分成两个不同的数组然后将它们连接在一起,但是这个任务有一些复杂性.

添加的任务规则是排序应保持一个恒定的额外空间,并在适当的位置修改数组.它还应该使用一种与数组大小一致的算法.

哪种算法？

从Wikipedia的列表来看,有许多算法可以一致地扩展并使用恒定的空间量.我还发现这个网站有一个很好的冒泡使用(也发布在下面),看起来很稳定,遵循我的规则(我想？).

我不确定这是否是正确的算法,或者如何完成这部分任务.

气泡:

  function comparator(a, b) {
    return a - b;
  }
  /**
   * Bubble sort algorithm.<br><br>
   * Complexity: O(N^2).
   *
   * @example
   * var sort = require('path-to-algorithms/src/' +
   * 'sorting/bubblesort').bubbleSort;
   * console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
   *
   * @public
   * @module sorting/bubblesort
   * @param {Array} array Input array.
   * @param {Function} cmp Optional. A function that defines an
   * alternative sort order. The function should return a negative,
   * zero, or positive value, depending on the arguments.
   * @return {Array} Sorted array.
   */
  function bubbleSort(array, cmp) {
    cmp = cmp || comparator;
    var temp;
    for (var i = 0; i < array.length; i += 1) {
      for (var j = i; j > 0; j -= 1) {
        if (cmp(array[j], array[j - 1]) < 0) {
          temp = array[j];
          array[j] = array[j - 1];
          array[j - 1] = temp;
        }
      }
    }
    return array;
  }

Answer 1

没有比较排序将线性扩展.幸运的是,您可以使用数组中的两个索引来执行此操作.这是基本的想法.

给定一个数组,a已经填充了.

startIndex = 0
endIndex = a.length - 1
while (startIndex < endIndex)
{
    // Skip over odd numbers at the front of the array
    while (startIndex < endIndex && (a[startIndex] % 2) != 0)
        ++startIndex;
    if (startIndex >= endIndex)
        break;
    // startIndex points to an even number
    // now look for the first odd number at the end of the array
    while (startIndex < endIndex && (a[endIndex] % 2) == 0)
        --endIndex;
    if (startIndex >= endIndex)
        break;
    // swap the two items, placing the even number
    // towards the end of the array, and the odd number
    // towards the front.
    temp = a[startIndex];
    a[startIndex] = a[endIndex];
    a[endIndex] = temp;
    // and adjust the indexes
    ++startIndex;
    --endIndex;
}

所以,给出你的示例数组:

[5, 2, 7, 9, 2, 3, 8, 4]

第一次通过循环,它发现索引1处的'2'是偶数.然后它从末尾向后搜索并在索引5处找到'3'.它交换它们:

[5, 3, 7, 9, 2, 2, 8, 4]

下一次通过循环,startIndex将是2,并且endIndex将startIndex增加超过'7'和'9',此时startIndex等于,endIndex并且您将跳出循环.

对于类似的问题和类似的算法,请参阅荷兰国旗问题.

Answer 2

尝试使用简单的排序,它可以满足您的期望

var data = [5, 2, 7, 9, 2, 3, 8, 4];
data.sort(function(a, b) {
  return b % 2 - a % 2
});
console.log(data);
// [5, 7, 9, 3, 2, 2, 8, 4]

// % is mod, 5 % 2 = 1; 2 % 2 = 0;

Answer 3

只需通过一个有条件地产生简单交换的索引,在O(1)空间的O(n)时间内,您可以执行以下操作.请注意,我已使用数组解构来交换.人们也可以选择使用临时变量.

function sortByParity(a){
  var ec = 0; // Even count
  for (var i = 0; i < a.length; i++){
    a[i] & 1 ? [a[i],a[i-ec]] = [a[i-ec],a[i]] // If odd then swap accordingly
             : ec++;                           // If even increment even count
  }
  return a;
}

var arr = [5,2,7,9,2,3,8,1,6,4],
    brr = [0,2,4,6,8,1,3,5,7,9],
    crr = [1,2,3,4,5,6,7,8,9,0];
console.log(JSON.stringify(sortByParity(arr)));
console.log(JSON.stringify(sortByParity(brr)));
console.log(JSON.stringify(sortByParity(crr)));

编辑:因为@Nina Scholz建议通过计算赔率可以以类似的方式实现相同的算法,但看起来可能更简单.(e & 1实际上与e % 2测试奇偶校验相同.赔率将导致1(真),而均衡将导致0(假))

function sortByParity(arr){
  var oc = 0;
  arr.forEach((e,i,a) => e & 1 && ([a[i], a[oc++]] = [a[oc], a[i]]));
  return arr;
}
              
var arr = [5,2,7,9,2,3,8,1,6,4],
    brr = [0,2,4,6,8,1,3,5,7,9],
    crr = [1,2,3,4,5,6,7,8,9,0];
console.log(JSON.stringify(sortByParity(arr)));
console.log(JSON.stringify(sortByParity(brr)));
console.log(JSON.stringify(sortByParity(crr)));