Javascript: сортировать массив и возвращать массив указателей, который указывает положение отсортированных элементов относительно исходных элементов

Предположим, что у меня есть массив 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].

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

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

Ответ 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]);
}

Edit

Вы, ребята, правы насчет 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(","));

Ответ 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);

Ответ 3

Дейв Аарон Смит прав, однако я думаю, что здесь интересно использовать 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});

Ответ 4

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 и к мутирующим массивам inline, но это позволяет сортировать массив любых объектов, которые можно сравнить. Требуется дополнительная функция, которая может использоваться для сортировки, подобно 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]

Ответ 5

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

Ответ 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);