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].

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

Существует ли существующий метод, который делает то, что я хочу?Если нет, как бы вы написали метод, который делает это?

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

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

Answer 3

Дейв Аарон Смит прав, однако я думаю, что здесь интересно использовать карту Array ().

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

Answer 4

Вы можете сделать это с помощью одной строки, используя 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)

Answer 5

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 о том, как вы относитесь к добавлению функций к прототипу 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]

Answer 6

Это более идиоматическая версия ответа 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);