Tôi muốn chia sẻ một mẹo mà tôi thường sử dụng trong C/C++ cho qsort().
JS 'sort() cho phép chỉ định hàm so sánh. Tạo mảng thứ hai có cùng độ dài và điền nó với số tăng từ 0.
function stableSorted(array, compareFunction) {
compareFunction = compareFunction || defaultCompare;
var indicies = new Array(array.length);
for (var i = 0; i < indicies.length; i++)
indicies[i] = i;
Đây là chỉ mục vào mảng ban đầu. Chúng ta sẽ sắp xếp mảng thứ hai. Tạo một hàm so sánh tùy chỉnh.
indicies.sort(function(a, b)) {
Nó sẽ lấy hai phần tử từ mảng thứ hai: sử dụng chúng làm chỉ mục vào mảng ban đầu và so sánh các phần tử.
var aValue = array[a], bValue = array[b];
var order = compareFunction(a, b);
if (order != 0)
return order;
Nếu các thành phần có thể bằng nhau, thì hãy so sánh các chỉ số của chúng để ổn định đơn đặt hàng.
if (a < b)
return -1;
else
return 1;
});
Sau khi sort(), mảng thứ hai sẽ chứa chỉ số mà bạn có thể sử dụng để truy cập vào các phần tử của mảng ban đầu trong ổn định trật tự sắp xếp.
var sorted = new Array(array.length);
for (var i = 0; i < sorted.length; i++)
sorted[i] = array[indicies[i]];
return sorted;
}
// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
a = String(a);
b = String(b);
if (a < b) return -1;
else if (a > b) return 1;
else return 0;
}
Nói chung, thuật toán sắp xếp ổn định chỉ trưởng thành và vẫn cần thêm bộ nhớ bổ sung so với qsort tốt. Tôi đoán đó là lý do tại sao rất ít thông số kỹ thuật ủy nhiệm sắp xếp ổn định.
Sẽ rất hữu ích nếu giữ cập nhật này. – ColBeseder
Có vẻ như Chrome (V8) sẽ giữ nguyên cách này: http://code.google.com/p/v8/issues/detail?id=90 –
http://ofb.net/~sethml/is-sort-stable .html? (Tôi đã lưu nó trên lưu trữ web chỉ trong trường hợp) – Pierre