Сортировка чисел в порядке убывания, но с `0` в начале

У меня есть проблема в JavaScript, которую я пытаюсь решить уже некоторое время.

Рассмотрим этот массив:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

Я должен вывести этот результат:

arr = [0, 0, 0, 0, 0, 5, 4, 3, 2, 1]

Я следую этой строке логики, чтобы расположить нули впереди, регулируя значение индекса:

arr.sort((x, y) => {
    if (x !== 0) {
        return 1;
    }

    if (x === 0) {
        return -1;
    }

    return y - x;
});

Но я застрял в этом результате:

arr = [0, 0, 0, 0, 0, 1, 2, 3, 4, 5]

У кого-нибудь есть какие-нибудь советы, как это решить?

Вы можете отсортировать по дельте bи a(для сортировки по убыванию) и принять Number.MAX_VALUEдля ложных значений, таких как ноль.

Эта:

Number.MAX_VALUE - Number.MAX_VALUE

равно нулю.

let array = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

array.sort((a, b) => (b || Number.MAX_VALUE) - (a || Number.MAX_VALUE));

console.log(...array);

Как сказано в MDN Docs:

Если a и b - два сравниваемых элемента, то:

Если compareFunction(a, b)возвращается меньше чем 0, сортируйте aпо индексу ниже чем b(то есть a стоит первым).

Если compareFunction(a, b)возвращается 0, оставьте a и b неизменными по отношению друг к другу, но отсортированные по всем различным элементам. Примечание: стандарт ECMAscript не гарантирует такого поведения, поэтому не все браузеры (например, версии Mozilla, датируемые как минимум 2003 годом) соблюдают это.

Если compareFunction(a, b) возвращается больше 0, сортируйте bпо индексу ниже, чем (т.е. bидет первым).

compareFunction(a, b)всегда должен возвращать одно и то же значение, если ему дана определенная пара элементов aи bдва аргумента. Если возвращаются противоречивые результаты, порядок сортировки не определен.

Итак, функция сравнения имеет следующий вид:

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

arr.sort((x, y) => {
    if (x > 0 && y > 0) {
        return y - x;
    }
    return x - y;
});

console.log(arr);

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

Особенно, если вы ожидаете значительное количество нулей, один проход по данным для их фильтрации должен быть намного лучше, чем выполнять более крупную O (N log N) сортировку, которая будет смотреть на каждый ноль несколько раз.

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

Также легко прочитать полученный код. Я использовал TypedArray, потому что он эффективен и упрощает сортировку чисел . Но вы можете использовать эту технику с обычным массивом, используя стандартную идиому (a,b)=>a-bдля .sort.

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let nonzero_arr = Int32Array.from(arr.filter(n => n != 0));
let zcount = arr.length - nonzero_arr.length;
nonzero_arr.sort();      // numeric TypedArray sorts numerically, not alphabetically

// Reverse the sorted part before copying into the final array.
nonzero_arr.reverse();

 // efficient-ish TypedArray for main result
let revsorted = new Int32Array(arr.length);   // zero-filled full size
revsorted.set(nonzero_arr, zcount);           // copy after the right number of zeros

console.log(Array.from(revsorted));      // prints strangely for TypedArray, with invented "0", "1" keys

/*
   // regular Array result
let sorted = [...Array(zcount).fill(0), ...nonzero_arr]  // IDK if this is efficient
console.log(sorted);
*/

Я не знаю, если TypedArray, .sort()а затем .reverseбыстрее, чем с помощью пользовательской функции сравнения для сортировки в порядке убывания. Или, если мы можем копировать и обратно на лету с итератором.

Также стоит подумать: используйте только один TypedArray полной длины .

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

Затем используйте .subarray()для получения нового представления TypedArray ненулевых элементов того же базового ArrayBuffer. Сортировка, в результате которой вы получите полный массив с нулевым началом и отсортированным хвостом, причем сортировка всегда будет рассматривать только ненулевые элементы.

Я не видел функции разделения в методах Array или TypedArray, но я почти не знаю JavaScript. При хорошем JIT цикл не должен быть намного хуже, чем встроенный метод. (Особенно, когда этот метод включает в себя функцию обратного вызова .filter, и если он не используется reallocпод капотом для сжатия, он должен выяснить, сколько памяти выделить, прежде чем он фактически отфильтровывается).

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

Просто измените условие вашей функции сравнения следующим образом:

let arr = [-1, 0, 1, 0, 2, -2, 0, 3, -3, 0, 4, -4, 0, 5, -5];
arr.sort((a, b) => {
   if(a && b) return b-a;
   if(!a && !b) return 0;
   return !a ? -1 : 1;
});

console.log(arr);

Не играю в гольф-код здесь:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, -1];
arr.sort(function(a, b) {
  if (a === 0 && b !== 0) {
    // a is zero b is nonzero, a goes first
    return -1;
  } else if (a !== 0 && b === 0) {
    // a is nonzero b is zero, b goes first
    return 1;
  } else {
    // both are zero or both are nonzero, sort descending
    return b - a;
  }
});
console.log(arr.toString());

Не пишите свою собственную числовую сортировку, если она уже существует. То, что вы хотите сделать, это именно то, что вы говорите в названии; сортировать числа в порядке убывания, кроме нулей в начале.

const zeroSort = arr => [...arr.filter(n => n == 0),
                         ...new Float64Array(arr.filter(n => n != 0)).sort().reverse()];

console.log(zeroSort([0, 1, 0, 2, 0, 3, 0, 4, 0, 500]));

Не пишите код, который вам не нужен; Вы можете ошибаться.

Выберите TypedArray в зависимости от того, какой тип чисел вы хотите обработать. Float64 является хорошим значением по умолчанию, поскольку он обрабатывает все обычные числа JS.

Вы можете сделать это так:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let result = arr.sort((a,b) => {
  if(a == 0 || b == 0)
    return a-b;
  return b-a;
})
console.log(result)

или вы можете сделать это:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let result = arr.sort().sort((a,b) => {
  if(a > 0 && b > 0)
    return b-a
  return 0
})

console.log(result)