JavaScript：对数组进行排序并返回一个索引数组，该数组指示排序后的元素相对于原始元素的位置。

Question

假设我有一个JavaScript数组，就像这样：

var test = ['b', 'c', 'd', 'a'];

我想对数组进行排序。显然，我可以使用以下方法来对数组进行排序：

test.sort(); //Now test is ['a', 'b', 'c', 'd']

但我真正想要的是一个索引数组，它指示已排序元素相对于原始元素的位置。我不太确定该如何表达这个需求，可能这就是我难以弄清楚如何实现它的原因。

如果有一个名为sortIndices()的方法，那么我想要的是：

var indices = test.sortIndices();
//At this point, I want indices to be [3, 0, 1, 2].

'在原始数组中，'a'位于第3个位置，'b'位于0号位置，'c'位于1号位置，'d'位于2号位置。因此，新数组为[3, 0, 1, 2]。 一种解决方法是对数组进行复制并排序，然后循环遍历排序后的数组并找到每个元素在原始数组中的位置。但是，这种方法感觉很笨拙。 是否有现有的方法可以实现我想要的功能？如果没有，你会如何编写一个实现此操作的方法？

- Jeremy

Answer 1

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

编辑

你们关于 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(","));

- Dave Aaron Smith

---

+1，但我认为最好不要在数组上使用 for .. in 循环。 - Tomalak

那是个好主意。我会试一下。（一旦它能正常工作，我就会接受。） - Jeremy

@Tomalak：我同意你关于for..in的看法。我也遇到了很多问题。 - Jeremy

在数组上使用for-in几乎总是一个非常糟糕的想法。 - strager

如果数组中包含undefined或null，则可能导致意外行为，请注意。 这是我的解决方案function getSortIndice(toSort: T[]): number[] { const sortingPair: [T, number][] = toSort.map((value, index) => [value, index]); sortingPair.sort((left, right) => { return (left[0] || 0) < (right[0] || 0) ? -1 : 1; // to be able to compare undefined }); const sortIndices: number[] = sortingPair.map(([t, indice]) => indice); return sortIndices; } - Zen3515

Answer 2

我会只将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);

- Sly1024

---

这很棒，而且可以更好一些（让排序稳定！）通过比较指数（a和b），如果值相等。即，将... test[a] > test[b] ? 1: 0更改为... test[a]> test[b]？1：a <b？-1：1，如下所示： https://dev59.com/qnM_5IYBdhLWcg3wUxZB - David Baird

还可以参考这个很棒的答案，它提供了一种（诚然不太高效）在一行中填充数组的方法。提示：let indices = [...Array(test.length).keys()];。 - Jeff G

尽管这个答案没有用任何紧凑的方式写出来，但我仍然认为这是最好的答案，因为它不改变现有的阵列结构，并且算法本身是解耦的，可以在任何混合和匹配的方式下重复使用。 - windmaomao

Answer 3

您可以通过一行代码实现这个功能（生成一个0->N-1的索引数组，并根据输入值进行排序）。

const test = ['b', 'c', 'd', 'a']
const result = Array.from(test.keys())
  .sort((a, b) => test[a].localeCompare(test[b]))
  
console.log(result)

- Matt Way

---

在我看来，这是最好的答案。不需要所有那些额外的映射，并且使用Array.keys()值得加1。 - milesaron

为什么不使用.sort((a,b) => test[b]-test[a])呢？ - Adam

@Adam 我可能漏掉了什么，但是这怎么可能行得通呢？例如 'b' - 'a' = NaN。 - Matt Way

@MattWay 抱歉，你是对的。我来这里问同样的问题，但我的数组是数字。 - Adam

@djvg 你说得对。已更新。旧答案，不确定我怎么会错过那个。 - Matt Way

Answer 4

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

- clerbois

Answer 5

这是一个更符合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);

- Dexygen

Answer 6

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

对于将函数添加到Array原型并在内联中改变数组的感受因人而异，但这使得可以对任何可比较对象的数组进行排序。它接受一个可选函数用于排序，类似于Array.prototype.sort。

例如：

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]

- Russ Cam

---

为什么不使用.apply而使用.call呢？ - strager

因为它在字母表中靠后 :) 老实说没有真正的理由，可能在这种情况下使用调用更有意义，因为这样就不需要每次创建数组。现在将进行更新。 - Russ Cam

Answer 7

你可以获取给定数组的索引，并根据它们的值进行排序。

const
    array = ['b', 'c', 'd', 'a'],
    indices = [...array.keys()].sort((a, b) => array[a].localeCompare(array[b]));

console.log(...indices);

- Nina Scholz

Answer 8

我们不需要触及数组的现有结构，相反，我们可以将额外的工作放在一边，这样我们就可以使功能更加模块化。

Array.prototype.sortIndices = function(compare) {
  const arr = this
  const indices = new Array(arr.length).fill(0).map((_, i) => i)

  return indices.sort((a, b) => compare(arr[a], arr[b]))
}

如果要用于char字符，请使用它。

test.sortIndices((a, b) => a.charCodeAt(0) - b.charCodeAt(0))

语法与 sort 相似。当然，只要 comp 的接口保持不变，您可以替换不同的排序算法。

在此运行：

var test = ['b', 'c', 'd', 'a']

Array.prototype.sortIndices = function(comp) {
    const indices = new Array(this.length)
        .fill(0).map((_, i) => i)
    return indices.sort((a, b) => comp(this[a], this[b]))
}

const { log } = console
log(test.sortIndices((a, b) => a.charCodeAt(0) - b.charCodeAt(0)))

- windmaomao

Answer 9

这是我基准测试中最快的方法：

var a=Array.from({length:10000},()=>Math.random())
var l=a.length,o=new Array(l)
for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)

这个方法与Sly1024的方法基本相同，只是它将数组的长度保存到一个变量中，而不是在每个for循环步骤中检查长度。如果我比较一个项目减去另一个项目的值而不是使用大于和小于运算符，如果我使用Array.from创建索引数组而不是使用for循环，如果我使用push而不是在索引处分配值，或者如果我没有初始化数组的长度，那么代码会变慢。

$ cat sortindexbench.js
var a=Array.from({length:1000},()=>Math.random())
var suite=new(require('benchmark')).Suite
suite.add('fastest',function(){
  var l=a.length,o=new Array(l);for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('length_not_saved_in_variable',function(){
  var o=new Array(a.length);for(var i=0;i<a.length;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('subtract_in_comparison_function',function(){
  var l=a.length;var o=new Array(l);for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]-a[r])
}).add('populate_array_of_indexes_with_array_from',function(){
  var r=Array.from(Array(a.length).keys()).sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('array_not_initialized_with_length',function(){
  var l=a.length;var o=[];for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('push_instead_of_assign_at_index',function(){
  var l=a.length;var o=new Array(l);for(var i=0;i<l;i++)o.push(i);o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('clerbois_and_Dexygen',function(){
  var o=a.map((v,i)=>{return{i,v}}).sort((l,r)=>l.v<r.v?-1:l.v>r.v?1:0).map((x)=>x.i)
}).add('clerbois_and_Dexygen_array_of_arrays_instead_of_object',function(){
  var o=a.map((v,i)=>[i,v]).sort((l,r)=>l[1]<r[1]?-1:l[1]>r[1]?1:0).map((x)=>x[0])
}).add('yakin_rojinegro',function(){
  var m=new Map();a.forEach((v,i)=>m.set(i,v));var o=Array.from(m.entries()).sort((l,r)=>l[1]<r[1]?-1:l[1]>r[1]?1:0).map(x=>x[0]);m.clear()
}).on('cycle',function(event){console.log(String(event.target))
}).on('complete',function(){console.log('Fastest is '+this.filter('fastest').map('name'))
}).run({'async':true})
$ npm i --save benchmark
[...]
$ node sortindexbench.js
fastest x 4,728 ops/sec ±0.15% (94 runs sampled)
length_not_saved_in_variable x 4,534 ops/sec ±3.19% (92 runs sampled)
subtract_in_comparison_function x 4,587 ops/sec ±0.30% (92 runs sampled)
populate_array_of_indexes_with_array_from x 4,205 ops/sec ±0.83% (94 runs sampled)
array_not_initialized_with_length x 4,638 ops/sec ±0.60% (96 runs sampled)
push_instead_of_assign_at_index x 4,510 ops/sec ±0.46% (95 runs sampled)
clerbois_and_Dexygen x 4,250 ops/sec ±0.86% (93 runs sampled)
clerbois_and_Dexygen_array_of_arrays_instead_of_object x 4,252 ops/sec ±0.97% (93 runs sampled)
yakin_rojinegro x 3,237 ops/sec ±0.42% (93 runs sampled)
Fastest is fastest

- nisetama

Answer 10

你可以使用 Array.prototype.entries() 来将项目与它们的索引配对。你也可以使用 Object.entries()，但这会将索引号转换为字符串。

let test = ["b", "c", "d", "a"];

console.log(
  Array.from(test.entries())
    .sort(([_, v], [__, w]) => v.localeCompare(w))
    .map(([i, _]) => i)
);

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

- loop