Javascript：排序数组并返回指示排序元素相对于原始元素的位置的索引数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3730510/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Javascript: Sort array and return an array of indicies that indicates the position of the sorted elements with respect to the original elements
提问by Jeremy
Suppose I have a Javascript array, like so:
假设我有一个 Javascript 数组，如下所示：
var test = ['b', 'c', 'd', 'a'];
I want to sort the array. Obviously, I can just do this to sort the array:
我想对数组进行排序。显然，我可以这样做来对数组进行排序：
test.sort(); //Now test is ['a', 'b', 'c', 'd']
But what I really want is an array of indices that indicates the position of the sorted elements with respect to the original elements. I'm not quite sure how to phrase this, so maybe that is why I am having trouble figuring out how to do it.
但我真正想要的是一个索引数组，它指示已排序元素相对于原始元素的位置。我不太确定如何表达这一点，所以也许这就是我无法弄清楚如何去做的原因。
If such a method was called sortIndices(), then what I would want is:
如果这样的方法被称为 sortIndices()，那么我想要的是：
var indices = test.sortIndices();
//At this point, I want indices to be [3, 0, 1, 2].
'a' was at position 3, 'b' was at 0, 'c' was at 1 and 'd' was a 2 in the original array. Hence, [3, 0, 1, 2].
'a' 位于位置 3，'b' 位于 0，'c' 位于 1，'d' 是原始数组中的 2。因此，[3, 0, 1, 2]。
One solution would be to sort a copy of the array, and then cycle through the sorted array and find the position of each element in the original array. But, that feels clunky.
一种解决方案是对数组的副本进行排序，然后循环遍历已排序的数组并找到每个元素在原始数组中的位置。但是，这感觉很笨拙。
Is there an existing method that does what I want? If not, how would you go about writing a method that does this?
是否有一种现有的方法可以满足我的要求？如果没有，您将如何编写执行此操作的方法？
采纳答案by Dave Aaron Smith
var test = ['b', 'c', 'd', 'a'];
var test_with_index = [];
for (var i in test) {
test_with_index.push([test[i], i]);
}
test_with_index.sort(function(left, right) {
return left[0] < right[0] ? -1 : 1;
});
var indexes = [];
test = [];
for (var j in test_with_index) {
test.push(test_with_index[j][0]);
indexes.push(test_with_index[j][1]);
}
Edit
编辑
You guys are right about for .. in. That will break if anybody munges the array prototype, which I observe annoyingly often. Here it is with that fixed, and wrapped up in a more usable function.
你们是对的for .. in。如果有人修改数组原型，那将会中断，我经常恼人地观察到它。这是固定的，并包含在一个更有用的功能中。
function sortWithIndeces(toSort) {
for (var i = 0; i < toSort.length; i++) {
toSort[i] = [toSort[i], i];
}
toSort.sort(function(left, right) {
return left[0] < right[0] ? -1 : 1;
});
toSort.sortIndices = [];
for (var j = 0; j < toSort.length; j++) {
toSort.sortIndices.push(toSort[j][1]);
toSort[j] = toSort[j][0];
}
return toSort;
}
var test = ['b', 'c', 'd', 'a'];
sortWithIndeces(test);
alert(test.sortIndices.join(","));
回答by Sly1024
I would just fill an array with numbers 0..n-1, and sort that with a compare function.
我只会用数字 0..n-1 填充一个数组，然后使用比较函数对其进行排序。
var test = ['b', 'c', 'd', 'a'];
var len = test.length;
var indices = new Array(len);
for (var i = 0; i < len; ++i) indices[i] = i;
indices.sort(function (a, b) { return test[a] < test[b] ? -1 : test[a] > test[b] ? 1 : 0; });
console.log(indices);
回答by clerbois
Dave Aaron Smith is correct, however I think it is interesting to use Array map() here.
Dave Aaron Smith 是正确的，但是我认为在这里使用 Array map() 很有趣。
var test = ['b', 'c', 'd', 'a'];
// make list with indices and values
indexedTest = test.map(function(e,i){return {ind: i, val: e}});
// sort index/value couples, based on values
indexedTest.sort(function(x, y){return x.val > y.val ? 1 : x.val == y.val ? 0 : -1});
// make list keeping only indices
indices = indexedTest.map(function(e){return e.ind});
回答by Matt Way
You can accomplish this with a single line using es6 (generating a 0->N-1index array and sorting it based on the input values).
您可以使用 es6 用一行完成此操作（生成0->N-1索引数组并根据输入值对其进行排序）。
var test = ['b', 'c', 'd', 'a']
var result = Array.from(Array(test.length).keys())
.sort((a, b) => test[a] < test[b] ? -1 : (test[b] < test[a]) | 0)
回答by Dexygen
This is a more idiomatic ES6 version of clerbois' answer, see his/hers for comments:
这是 clerbois 回答的更惯用的 ES6 版本，请参阅他/她的评论：
return test.map((val, ind) => {return {ind, val}})
.sort((a, b) => {return a.val > b.val ? 1 : a.val == b.val ? 0 : -1 })
.map((obj) => obj.ind);
回答by Russ Cam
Array.prototype.sortIndices = function (func) {
var i = j = this.length,
that = this;
while (i--) {
this[i] = { k: i, v: this[i] };
}
this.sort(function (a, b) {
return func ? func.call(that, a.v, b.v) :
a.v < b.v ? -1 : a.v > b.v ? 1 : 0;
});
while (j--) {
this[j] = this[j].k;
}
}
YMMV on how you feel about adding functions to the Array prototype and mutating arrays inline, but this allows sorting of an array of any objects that can be compared. It takes an optional function that can be used for sorting, much like Array.prototype.sort.
YMMV 关于向 Array 原型添加函数和内联改变数组的感受，但这允许对可以比较的任何对象的数组进行排序。它需要一个可用于排序的可选函数，就像Array.prototype.sort.
An example,
一个例子，
var test = [{b:2},{b:3},{b:4},{b:1}];
test.sortIndices(function(a,b) { return a.b - b.b; });
console.log(test); // returns [3,0,1,2]
