Javascript: Ordina array e restituire un array di indicies che indica la posizione degli elementi ordinati con rispetto agli elementi originali

Question

Supponiamo che io sono un array di Javascript, in questo modo:

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

voglio ordinare l'array . Ovviamente, posso solo fare questo per ordinare l'array:

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

Ma quello che voglio davvero è un array di indici che indica la posizione degli elementi ordinati con rispetto agli elementi originali. Non sono del tutto sicuro su come esprimerlo, quindi forse è per questo che ho difficoltà a capire come farlo.

Se un tale metodo è stato chiamato sortIndices(), quindi quello che vorrei è:

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

'un' era in posizione 3, 'b' era a 0, 'c' era a 1 e 'd' era un 2 nella matrice originale. Quindi, [3, 0, 1, 2].

Una soluzione consiste nell'ordinare una copia dell'array, quindi scorrere l'array ordinato e trovare la posizione di ciascun elemento nell'array originale. Ma questo sembra goffo.

Esiste un metodo esistente che fa ciò che voglio? Se no, come andresti a scrivere un metodo che faccia questo?

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

Modifica

Voi ragazzi sono di destra circa for .. in. Questo si interromperà se qualcuno muterà il prototipo dell'array, che osservo spesso fastidiosamente. Qui è con quello fisso, e avvolto in una funzione più utilizzabile.

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

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 su come ci si sente di aggiungere funzioni al prototipo Array e mutando gli array in linea, ma questo permette l'ordinamento di un array di oggetti che possono essere confrontate. Prende una funzione opzionale che può essere utilizzata per l'ordinamento, molto simile a Array.prototype.sort.

Un esempio

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 3

Vorrei inserite un array con numeri 0..n-1, e ordinare che con una funzione di confronto.

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 4

Dave Aaron Smith è corretto (non posso commentare), tuttavia penso che sia interessante utilizzare la mappa di array() qui.

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 5

Ciò può essere eseguito con una singola linea utilizzando ES6 (generando una matrice 0->N-1 indice e smistamento sulla base dei valori di ingresso).

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)