使用 JavaScript 减少函数对数组进行排序

Sorting Array with JavaScript reduce function

提问by AmerllicA

Often I study some JavaScriptinterview questions, suddenly I saw a question about usage of reducefunction for sorting an Array, I read about it in MDNand the usage of it in some mediumarticles, But sorting an Arrayis so Innovative:

经常研究一些面JavaScript试题，突然看到一个关于reduce函数排序an的用法的问题Array，我在MDN上看过，在一些medium文章中也看到了它的用法，但是排序anArray太有创意了：

const arr = [91,4,6,24,8,7,59,3,13,0,11,98,54,23,52,87,4];

I thought a lot, but I've no idea about how answer this question, how must be the reducecall backfunction? what is the initialValueof reducefunction? And what are the accumulatorand currentValueof call backfunction of reduce?

我想了很多，但我不知道如何回答这个问题，reducecall back函数必须如何？是什么initialValue的reduce功能？什么是accumulator和currentValue中call back的作用reduce？

And at the end, does this way have some benefits than other sorting algorithms? Or Is it useful to improve other algorithms?

最后，这种方式是否比其他排序算法有一些好处？或者改进其他算法有用吗？

采纳答案by Jonas Wilms

It makes no sense to use reduce here, however you could use a new array as an accumulator and do insertion sort with all elements:

在这里使用 reduce 是没有意义的，但是您可以使用一个新数组作为累加器并对所有元素进行插入排序：

array.reduce((sorted, el) => {
  let index = 0;
  while(index < array.length && el < array[index]) index++;
  sorted.splice(index, 0, el);
  return sorted;
}, []);

Here is the version withoutreduce:

这是没有减少的版本：

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

---

---

Now some general tips for writing reducers:

现在有一些编写 reducer 的一般提示：

how must be the reduce call back function?

减少回调函数必须如何？

You either take an approach with an accumulator, then the reducer should apply a modification to the accumulator based on the current element and return it:

您要么采用累加器的方法，然后减速器应根据当前元素对累加器应用修改并返回它：

(acc, el) => acc

Or if accumulator and the elements have the sane type and are logically equal, you dont need to distinguish them:

或者，如果 accumulator 和元素具有健全的类型并且在逻辑上是相等的，则不需要区分它们：

 (a, b) => a + b

what is the initialValue of reduce function?

reduce 函数的初始值是多少？

You should ask yourself "What should reduce return when it is applied on an empty array?"

你应该问自己“当它应用于空数组时，什么应该减少回报？”

Now the most important: When to use reduce? (IMO)

现在最重要的是：什么时候使用reduce？(海事组织)

If you want to boil down the values of an array into one single value or object.

如果您想将数组的值归结为一个值或对象。

回答by Lex

Array.sortmutates the array where using Array.reduceencourages a pure function. You could clone the array before sorting.

Array.sort改变数组，其中 usingArray.reduce鼓励纯函数。您可以在排序之前克隆数组。

I believe this question is designed to get you thinking differently by enforcing constraints. It tests your knowledge of how reduceworks and as the answers show there are many ways to skin a cat. It'll show your personal flavour of js in solving this.

我相信这个问题旨在通过强制约束让您以不同的方式思考。它测试您对reduce工作原理的了解，正如答案所示，有很多方法可以给猫剥皮。它会在解决这个问题时展示你个人的 js 风格。

I chose to use Array.findIndexand Array.splice.

我选择使用Array.findIndex和Array.splice。

const sortingReducer = (accumulator, value) => {
  const nextIndex = accumulator.findIndex(i => value < i );
  const index = nextIndex > -1 ? nextIndex : accumulator.length;
  accumulator.splice(index, 0, value);
  return accumulator;
}

const input = [5,4,9,1];
const output = input.reduce(sortingReducer, []);

Testing with the sample input produces

使用样本输入进行测试会产生

arr.reduce(sortingReducer, [])
// (17)?[0, 3, 4, 4, 6, 7, 8, 11, 13, 23, 24, 52, 54, 59, 87, 91, 98]

回答by JollyJoker

Here's an (imo) more elegant version of Jonas W'sinsertion sort solution. The callback just builds a new array of all lower values, the new one and all higher values. Avoids using explicit loops or indices, so it's easier to see at a glance that it works correctly.

这是Jonas W 的插入排序解决方案的（imo）更优雅的版本。回调只是构建一个包含所有较低值、新值和所有较高值的​​新数组。避免使用显式循环或索引，因此更容易一目了然地看到它是否正常工作。

const insertValue = (arr, value) =>
  [...arr.filter(n => n <= value), value, ...arr.filter(n => n > value)]

const testArr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4]

console.log(testArr.reduce(insertValue, []))

回答by Maxim

reduceconstraints yourself to online sorting algorithms, where each element in the array is seen once and you do not now in advance the length of your array (note that using closures you could give more information to the reducing function but this kinds of defeats the purpose of the question).

reduce将自己限制在在线排序算法中，其中数组中的每个元素都被看到一次，而您现在不预先知道数组的长度（请注意，使用闭包可以为减少函数提供更多信息，但这种方式违背了问题）。

insertion sort is an obvious and easy example; I won't detail the implementation as the other answers are already very good in this regard. However you can mention a few optimizations that might probably seen as very positive to the interviewer:

插入排序是一个明显而简单的例子；我不会详细说明实现，因为其他答案在这方面已经非常好。但是，您可以提及一些可能对面试官非常积极的优化：

• Use binary search to find the insertion point can reduce the complexity of an insertion step from O(n) to O(log n). This is called binary insertion sort: the overall number of comparisons will go from O(n^2) to O(n log n). This won't be faster because the real cost is due to "splicing" the output array but if you had expensive comparisons (say, sorting long strings for instance) it could make a difference.

• If you sort integer, you can use radix sortand implement a linear online sorting algorithm with reduce. This is quite trickier to implement, but very suited to a reduction.

• 使用二分查找找到插入点可以将一个插入步骤的复杂度从 O(n) 降低到 O(log n)。这称为二元插入排序：比较的总数将从 O(n^2) 到 O(n log n)。这不会更快，因为真正的成本是由于“拼接”输出数组，但如果您进行了昂贵的比较（例如，对长字符串进行排序），它可能会有所作为。

• 如果对整数进行排序，则可以使用基数排序并使用reduce 实现线性在线排序算法。这实现起来相当棘手，但非常适合减少。

回答by brk

Here is an example of the sortingan array in descending order using reduce function.

这是sorting使用reduce函数按降序排列数组的示例。

what is the initialValue of reduce function

什么是reduce函数的initialValue

In this below function the initial value is the []which is passed as thisArgin the reduce function.

在这个下面的函数中，初始值是在reduce函数中[]传递的thisArg。

 array.reduce(function(acc,curr,currIndex,array){
        //rest of the code here
        },[]//this is initial value also known as thisArg)

So basically an empty array is passed and the elements will be be pushed to this array

所以基本上传递了一个空数组，元素将被推送到这个数组

The accumulator here is the empty array.

这里的累加器是空数组。

const arr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];
var m = arr.reduce(function(acc, cur) {
  // this arrVar will have the initial array
  let arrVar = arr;
  // get the max element from the array using Math.max
  // ... is spread operator
  var getMaxElem = Math.max(...arrVar);
  // in the accumulator we are pushing the max value
  acc.push(getMaxElem);
  // now need to remove the max value from the array, so that next time it 
  // shouldn't not be considered
  // splice will return a new array
  // now the arrVar is a new array and it does not contain the current
  // max value
  arrVar = arrVar.splice(arrVar.indexOf(getMaxElem), 1, '')
  return acc;
}, []);
console.log(m)

回答by gschenk

A terrible sorting algorithm can be written in a one liner with ES6:

一个糟糕的排序算法可以用 ES6 写成一行：

const sorter = (xs, x) => xs.slice(-1)[0] >= x ? [x, ...xs] : [...xs, x];

If the present element is larger or equal the last element of the previously sorted list it is appended to the end, otherwise to the beginning.

如果当前元素大于或等于先前排序列表的最后一个元素，则将其附加到末尾，否则附加到开头。

[3,4,1].reduce(sorter,[]).reduce(sorter,[])

//returns [1,3,4]

It takes several applications to its return to sort anything but the most simple arrays.

除了最简单的数组之外，它需要几个应用程序才能返回排序。

But it will eventually get there. That calls for a recursion!

但它最终会到达那里。这需要递归！

const arr = [91,4,6,24,8,7,59,3,13,0,11,98,54,23,52,87,4];

const sorter2 =(as) => as.reduce(
  (xs, x) => x >= xs.slice(-1)[0] ? [...xs, x] 
    : xs[0] < x ? sorter2([x, ...xs])
    : [x, ...xs],
  [],
);

const result = sorter2(arr);

console.log(result.join(', '));

When the present value is larger than the last value of already processed array it is appended. If it is smaller than the first element it is prepended. Only if it is neither before or after the the present value and the accumulated array are sorted again by a recursive call. The method should be equivalent to an insertion sort (please comment!).

当当前值大于已处理数组的最后一个值时，它被追加。如果它小于第一个元素，则将其添加到前面。仅当它既不在当前值之前也不在当前值之后，并且累积的数组通过递归调用再次排序。该方法应该等同于插入排序（请注释！）。

回答by MT0

You can use an insertion sort:

您可以使用插入排序：

let array        = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];
let countIfLess  = (array,v)=> array.reduce((c,n)=>n<v?c+1:c,0);
let countIfEqual = (array,v)=> array.reduce((c,n)=>n==v?c+1:c,0);

console.log(
  array.reduce(
    (a,v,i,array)=>( a[countIfLess(array,v) + countIfEqual(a,v)]=v, a ),
    new Array(array.length)
  )
);

This will create the destination array once and then perform insertions into it at each step of the reduce without having to recreate the destination array.

这将创建一次目标数组，然后在 reduce 的每个步骤中执行插入操作，而无需重新创建目标数组。

There are more efficient ways of implementing countIfEqualbut I chose to implement all the functions using reducerather than other array functions.

有更有效的实现方式，countIfEqual但我选择使用reduce而不是其他数组函数来实现所有函数。

回答by Nina Scholz

You could use some functions for getting an array if not an array is supplied, a function which returns a sorted array by taking two parameters and a sort callback which includes the above by using another reduce method for getting a part result of a sorted array.

如果没有提供数组，您可以使用一些函数来获取数组，一个函数通过接受两个参数返回一个排序的数组，一个排序回调包括上面的通过使用另一种减少方法获取排序数组的部分结果。

const
    getArray = a => Array.isArray(a) ? a : [a],
    order = (a, b) => a < b ? [a, b] : [b, a],
    sort = (a, b) => getArray(a).reduce((r, v) => r.concat(order(r.pop(), v)), [b]),
    array = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];

console.log(array.reduce(sort));

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

回答by Nikhil Aggarwal

Though, reduce is not ideally meant for the sorting. The following solution is just like a forEachor any loop function trying to be achieved with Array.reducefunction.

但是，reduce 并不是排序的理想选择。下面的解决方案就像一个forEach或任何试图用Array.reduce函数实现的循环函数。

var arr = [91,4,6,24,8,7,59,3,13,0,11,98,54,23,52,87,4];

arr = arr.reduce(function(acc,val){
  
  if(acc.length) {
    var temp = [];
    while(acc[acc.length -1] > val) {
      temp.push(acc.pop());
    } 
    acc.push(val);
    while(temp.length) {
      acc.push(temp.pop());
    }
  } else {
    acc.push(val);  
  }
  return acc;
  
}, []);

console.log(arr);

Please note, you can use the native function Array.sortfor sorting and can also have your own custom sort function where you can define your own sorting algorithm.

请注意，您可以使用本机函数Array.sort进行排序，也可以拥有自己的自定义排序函数，您可以在其中定义自己的排序算法。