按降序对数字进行排序，但开头应为0

Question

我在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]

有没有人有解决此问题的提示？

Answer 1

您可以通过三角洲排序b和a（对于降序排序），并采取Number.MAX_VALUE为falsy值像为零。

这个：

Number.MAX_VALUE - Number.MAX_VALUE

等于零。

Number.MAX_VALUE - Number.MAX_VALUE

Answer 2

正如mdn docs所说：

如果a和b是要比较的两个元素，则：

如果compareFunction(a, b)返回小于0，则排序a到小于的索引b（即a排在前）。

如果compareFunction(a, b)返回0，则使a和b相对不变，但对所有不同元素进行排序。注意：ECMAscript标准不保证此行为，因此，并非所有浏览器（例如，至少可追溯到2003年的Mozilla版本）都遵守此规定。

如果compareFunction(a, b) 返回值大于0，则排序b到小于a的索引（即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;
}

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

Answer 3

If you care about efficiency, it's probably fastest to filter out the zeros first. You don't want sort to waste time even looking at them, let alone adding extra work to your comparison callback to handle that special case.

Especially if you expect a significant number of zeros, one pass over the data to filter them out should be much better than doing a larger O(N log N) sort that will look at each zero multiple times.

You can efficiently prepend the right number of zeros after you're done.

It's also just as easy to read the resulting code. I used TypedArray because it's efficient and makes numeric sorting easy. But you can use this technique with regular Array, using the standard idiom of (a,b)=>a-b for .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);
*/

I don't know if TypedArray .sort() and then .reverse is faster than using a custom comparison function to sort in descending order. Or if we can copy-and-reverse on the fly with an iterator.

Also worth considering: only use one TypedArray of the full length.

Instead of using .filter, loop over it and swap the zeros to the front of the array as you go. This takes one pass over your data.

Then use .subarray() to get a new TypedArray view of the non-zero elements of the same underlying ArrayBuffer. Sorting that will leave you the full array with a zero start and a sorted tail, with the sort only ever looking at the non-zero elements.

I didn't see a partition function in the Array or TypedArray methods, but I barely know JavaScript. With good JIT, a loop shouldn't be too much worse than a built-in method. (Especially when that method involves a callback like .filter, and unless it uses realloc under the hood to shrink, it has to figure out how much memory to allocate before it actually filters).

I used regular-Array .filter() before converting to a TypedArray. If your input is already a TypedArray you don't have this problem, and this strategy gets even more attractive.

Answer 4

只需像这样修改您的比较功能的条件-

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

Answer 5

如果已经存在，请不要编写自己的数字排序。你想要做的正是你在标题中所说的；以降序对数字进行排序，开头的零除外。

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 数字。

Answer 6

在这里不玩代码高尔夫：

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