Javascript: Array sortieren und ein Array von Indizes zurückgeben, das die Position der sortierten Elemente in Bezug auf die ursprünglichen Elemente angibt

Angenommen, ich habe ein Javascript-Array wie folgt:

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

Ich möchte das Array sortieren. Offensichtlich kann ich das nur tun, um das Array zu sortieren:

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

Aber was ich wirklich will, ist ein Array von Indizes, das die Position der sortierten Elemente in Bezug auf die ursprünglichen Elemente angibt. Ich bin mir nicht ganz sicher, wie ich das formulieren soll, vielleicht habe ich deshalb Probleme, herauszufinden, wie es geht.

Wenn eine solche Methode sortIndices() genannt würde, dann würde ich Folgendes wollen:

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

‘a’ war an Position 3, ‘b’ war an 0, ‘c’ war an 1 und ‘d’ war eine 2 im ursprünglichen Array. Somit, [3, 0, 1, 2].

Eine Lösung wäre, eine Kopie des Arrays zu sortieren und dann das sortierte Array zu durchlaufen und die Position jedes Elements im ursprünglichen Array zu finden. Aber das fühlt sich klobig an.

Gibt es eine vorhandene Methode, die das tut, was ich will? Wenn nicht, wie würden Sie vorgehen, um eine Methode zu schreiben, die dies tut?

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

Bearbeiten

Ihr habt Recht for .. in. Das wird brechen, wenn jemand den Array-Prototyp munged, was ich ärgerlich oft beobachte. Hier ist es damit behoben und in eine brauchbarere Funktion verpackt.

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

Ich würde einfach ein Array mit den Zahlen 0..n-1 füllen und das mit einer Vergleichsfunktion sortieren.

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

Sie können dies mit einer einzigen Zeile mit es6 erreichen (Erzeugung einer 0->N-1 index-Array und Sortierung basierend auf den Eingabewerten).

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)

console.log(result)

Dave Aaron Smith hat Recht, aber ich denke, es ist interessant, hier Array map() zu verwenden.

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

Dies ist eine idiomatischere ES6-Version der Antwort von Clerbois, siehe ihre Kommentare:

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

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, wie Sie über das Hinzufügen von Funktionen zum Array-Prototyp und das Mutieren von Arrays inline denken, aber dies ermöglicht das Sortieren eines Arrays beliebiger Objekte, die verglichen werden können. Es nimmt eine optionale Funktion an, die zum Sortieren verwendet werden kann, ähnlich wie Array.prototype.sort.

Ein Beispiel,

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]

Sie können dies mit dem Map-Objekt tun. Legen Sie einfach den Schlüssel/Wert als Index/Wert fest und verwenden Sie Array.from, um den Iterator als zweidimensionales Array zu erhalten, und sortieren Sie dann entweder die Indizes, die Werte oder beides.

function sorting(elements) {
  const myMap = new Map();
  elements.forEach((value, index) => {
    myMap.set(index, value);
  });
  const arrayWithOrderedIndexes = Array.from(myMap.entries()).sort((left, right) => {return left[1] < right[1] ? -1 : 1});
  myMap.clear();
  return arrayWithOrderedIndexes.map(elem => elem[0]);
}
const elements = ['value','some value','a value','zikas value','another value','something value','xtra value'];
sorting(elements);