Сортируйте массив целых чисел в нечетные, тогда даже

Ответ 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]

Первый раз через цикл он обнаруживает, что "2" в индексе 1 четный. Затем он ищет назад от конца и находит "3" в индексе 5. Он меняет их:

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

В следующий раз через цикл, startIndex будет равно 2, а endIndex будет 4. startIndex будет увеличиваться за "7" и "9", когда startIndex будет равно endIndex и вы выходите из цикла.

Для аналогичной проблемы и аналогичного алгоритма см. проблема голландского национального флага.

Ответ 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;

Ответ 3

Просто одним индексом, условно дающим простые свопы, в O (n) время в O (1) пространстве вы можете сделать следующее. Обратите внимание, что я использовал деструктурирование массива для обмена. Можно также использовать временную переменную.

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)));

Ответ 4

Вы можете отсортировать массив на месте в постоянном пространстве, используя аналогичную методологию для популярных алгоритмов сортировки.

Имейте переменную, чтобы пометить индексы отсортированных в данный момент частей массива, а затем выполнить работу между элементами, находящимися между ними или оставив их на месте (в случае их нечетности - на месте уже отсортировано), или доводя их до конца, если они ровные.

Этот алгоритм O(n), а размер пространства - это размер массива. Оба они масштабируются линейно с размером массива.

var data = [5, 2, 7, 9, 2, 3, 8, 4];

// end holds the position of the last unsorted number
var end = data.length - 1;
// start holds the position of the first unsorted number
var start = 0;
// position is the current index of the number which is of interest 
var position = start;

// while the two sorted halves have not met
while (start < end) {
  var subject = data[position];
  if (subject % 2 === 1) {
    // it odd, it already in the correct half of the array
    // so move to the next number, and increase start, marking this
    // number as sorted
    position++;
    start++;
  } else {
    // it even, move it to the even sorted section. The means that
    // the number in "position" has not been looked at yet, so do not
    // increase "position", but there an extra sorted number at the
    // end, so decrease "end"
    var temp = data[end];
    data[end] = subject;
    data[position] = temp;
    end--;
  }
}

console.log(data);

Ответ 5

Множество реализаций уже опубликовано, поэтому я хотел бы указать, как эта проблема уже решена в основном в любой инфраструктуре.

При атаке на этот вопрос, поучительно смотреть на quicksort. Или не быстро сортировать, а подоперацию quicksort "partition", которая решает практически ту же проблему.

Подоперация "partition" выполняет следующую задачу: учитывая последовательность чисел и сводную точку, на месте переставляйте элементы последовательности таким образом, чтобы все числа, меньшие, чем точка поворота, находились в левой части последовательности, а все числа, большие, чем точка поворота, находятся в правой части последовательности. (Числа, равные поворотному концу, посередине, но если вы не пытаетесь реально сделать это неправильно, это произойдет автоматически.)

Это почти то, что мы пытаемся сделать здесь: In-place переставить элементы таким образом, чтобы они были разделены на две стороны на основе двоичного теста. Для быстрой сортировки это меньше; для этой проблемы это нечетно.

Итак, если вы рассматриваете проблему такого характера (локальный раздел на основе бинарного предиката), наиболее удобным способом атаки является копирование вашей операции с разделом кода. Единственное релевантное соображение состоит в том, что здесь нет точки опоры, поэтому имейте в виду, к чему стремилась оперативная сортировка, и не пропускайте этот индекс.

Ответ 6

Если вы соглашаетесь дублировать память, вы можете сделать это с помощью простых старых функций JavaScript, так как вы не хотите, чтобы подмассивы сами сортировались:

var res = [];
for(var i = 0; i < input.length; ++i)
  If (input [i] % 2)
      res.unshift (input[i])
  else
      res.push(input [i])

Ответ 7

Да, ваша первая идея вычислить четные и четные числа была в порядке:

var input = [5, 2, 7, 9, 2, 3, 8, 4];
var result = input.filter(x => x%2).sort().concat(input.filter(x => x%2 === 0).sort());
console.log(result);

Ответ 8

Начните один указатель с фронта, который останавливается при четных значениях, а другой - от последнего, который останавливается при нечетных значениях. Поменяйте два значения и продолжайте, пока оба указателя не пересекаются друг с другом.

Кроме того, этот алгоритм имеет сложность O (n).

function SortThisArray(arr) {

  var startIndex = 0;
  var endIndex = arr.length - 1;

  while(startIndex < endIndex) {

    if(arr[startIndex] % 2 == 0 && arr[endIndex] % 2 == 1) {
      var temp = arr[startIndex];
      arr[startIndex] = arr[endIndex];
      arr[endIndex] = temp;
    }

    if(arr[startIndex] % 2 == 1) 
      startIndex++;      

    if(arr[endIndex] % 2 == 0)
      endIndex--;
  }

  return arr;
}

Ответ 9

Это предложение, которое ищет непрерывные пары четных и неравномерных чисел. Когда он найден, пара свопит.

Алгоритм поддерживает порядок групп нечетных и четных чисел.

В основном он использует счетчик индексов и цикл while с механизмом отслеживания назад, если пара найдена, тогда индекс, если больше нуля, уменьшается.

Например, это прохождение массива:

        array                        comment
---------------------    --------------------------------
5 7 2 8 7 9 2 1 4 6 8    found even odd couple at index 3
      ^ ^                swap items, decrement index by 1
5 7 2 7 8 9 2 1 4 6 8    found even odd couple at index 2
    ^ ^
5 7 7 2 8 9 2 1 4 6 8    found even odd couple at index 4
        ^ ^
5 7 7 2 9 8 2 1 4 6 8    found even odd couple at index 3
      ^ ^
5 7 7 9 2 8 2 1 4 6 8    found even odd couple at index 6
            ^ ^
5 7 7 9 2 8 1 2 4 6 8    found even odd couple at index 5
          ^ ^
5 7 7 9 2 1 8 2 4 6 8    found even odd couple at index 4
        ^ ^
5 7 7 9 1 2 8 2 4 6 8    final result

var a = [5, 2, 7, 8, 7, 9, 2, 1, 4, 6, 8],
    i = 0,
    temp;

while (i < a.length - 1) {
    if (!(a[i] % 2) && a[i + 1] % 2) {
        temp = a[i];      
        a[i] = a[i + 1];
        a[i + 1] = temp;
        i && i--;
        continue;
    }
    i++;
}

console.log(a); // [5, 7, 7, 9, 1, 2, 8, 2, 4, 6, 8]

.as-console-wrapper { max-height: 100% !important; top: 0; }

Ответ 10

По мне, это самый простой способ - если вам нужно объяснение, прочитайте ответ @Dinesh Verma

Это один проход и использование только 3 переменных в качестве дополнительного хранилища

function sort(list)
{
  var bottom=0
  var top=list.length-1
  var swap
  while(bottom < top)
  {
    if (list[bottom] % 2 == 1) 
      ++bottom
    else if (list[top] % 2 == 0)
      --top
    else {
      swap = list[bottom]
      list[bottom] = list[top]
      list[top] = swap

    }
  }
  return list 
}