Я хотел бы поделиться трюком, который я обычно использую в C / C ++ для qsort().
JS 'sort () позволяет указать функцию сравнения.Создайте второй массив такой же длины и заполните его возрастающими числами от 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;
Это индексы в исходном массиве.Мы собираемся отсортировать второй массив.Создайте пользовательскую функцию сравнения.
indicies.sort(function(a, b)) {
Она получит два элемента из второго массива: используйте их как индексы в исходных массивах и сравните элементы.
var aValue = array[a], bValue = array[b];
var order = compareFunction(a, b);
if (order != 0)
return order;
Если элементысовпадают, затем сравните их индексы, чтобы сделать порядок стабильным.
if (a < b)
return -1;
else
return 1;
});
После сортировки () второй массив будет содержать индексы, которые можно использовать для доступа к элементам исходного массива в стабильной сортировке.order.
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;
}
В общем, алгоритмы стабильной сортировки только созревают и по-прежнему требуют больше дополнительной памяти по сравнению с хорошей сортировкой.Наверное, поэтому очень немногие спецификации требуют стабильной сортировки.