javascript: Sắp xếp mảng và trả về một mảng của indicies cho biết vị trí của các nguyên tố được sắp xếp liên quan đến các yếu tố gốc

Question

Giả sử tôi có một mảng javascript, như vậy:

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

Tôi muốn sắp xếp mảng . Rõ ràng, tôi chỉ có thể làm điều này để sắp xếp mảng:

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

Nhưng điều tôi thực sự muốn là một chỉ số cho biết vị trí của các yếu tố được sắp xếp đối với các phần tử gốc. Tôi không chắc chắn làm thế nào để cụm từ này, vì vậy có lẽ đó là lý do tại sao tôi gặp khó khăn trong việc tìm ra cách để làm điều đó.

Nếu một phương pháp như vậy được gọi là sortIndices(), sau đó là những gì tôi muốn là:

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

'a' là ở vị trí 3, 'b' là 0, 'c' là 1 và 'd' là 2 trong mảng ban đầu. Do đó, [3, 0, 1, 2].

Một giải pháp sẽ là sắp xếp một bản sao của mảng, sau đó quay vòng qua mảng được sắp xếp và tìm vị trí của từng phần tử trong mảng ban đầu. Nhưng, điều đó cảm thấy vụng về.

Có phương pháp hiện tại nào thực hiện những gì tôi muốn không? Nếu không, làm thế nào bạn sẽ đi về viết một phương pháp thực hiện điều này?

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

Sửa

Các bạn có quyền về for .. in. Điều đó sẽ phá vỡ nếu bất cứ ai nghiền nguyên mẫu mảng, mà tôi quan sát thường xuyên khó chịu. Ở đây nó là với cố định, và bọc trong một chức năng dễ sử dụng hơn.

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 vào cách bạn cảm nhận về việc thêm chức năng để nguyên mẫu Array và đột biến mảng nội tuyến, nhưng điều này cho phép sắp xếp của một mảng của bất kỳ đối tượng có thể được so sánh. Nó có một chức năng tùy chọn có thể được sử dụng để phân loại, giống như Array.prototype.sort.

Một ví dụ,

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

tôi sẽ chỉ cần điền một mảng với số 0..n-1, và sắp xếp rằng với một chức năng so sánh.

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 là chính xác (tôi không thể nhận xét), tuy nhiên tôi nghĩ thú vị khi sử dụng bản đồ Array() tại đây.

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

Bạn có thể thực hiện điều này với một dòng duy nhất sử dụng es6 (tạo ra một mảng 0->N-1 chỉ số và phân loại nó dựa trên các giá trị đầu vào).

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)