Я знаю, что спецификация сценария ECMA не указывает, какой алгоритм использовать для сортировки массивов, и не указывает, должна ли сортировка быть стабильной.
Я нашел эту информацию для Firefox который указывает, что firefox использует стабильную сортировку.
Кто-нибудь знает про IE 6/7/8, Chrome и Safari?
Начиная с ES2019, sort должен быть стабильным. В ECMAScript от 1-й редакции до ES2018 разрешалось работать нестабильно.
Простой тестовый пример (заголовок игнорируется, второй набор чисел должен быть последовательным если сорт двигателя стабильный). Примечание. Этот тестовый пример не работает для некоторых версий Chrome (технически V8), которые переключают алгоритмы сортировки в зависимости от размера массива, используя стабильную сортировку для небольших массивов, но нестабильную для больших массивов. (Подробности.) См. конец вопроса для измененного версия, которая делает массив достаточно большим, чтобы вызвать поведение.
Сортировка IE была стабильной, пока я ее использовал (например, IE6). Еще раз проверяю в IE8, и похоже, что это все еще так.
И хотя на той странице Mozilla, на которую вы ссылаетесь, говорится, что сортировка Firefox стабильна, я определенно говорю, что это не всегда было так до (и включая) Firefox 2.0.
Некоторые беглые результаты:
Все тесты на винде.
См. также: Быстрая стабильная реализация алгоритма сортировки в javascript < / а>
Этот тестовый пример (измененный из здесь) продемонстрирует проблему в V8 ( например, Node v6, Chrome ‹v70), убедившись, что в массиве достаточно записей для выбора« более эффективного »метода сортировки; это написано с учетом очень старых движков JavaScript, поэтому без современных функций:
function Pair(_x, _y) {
this.x = _x;
this.y = _y;
}
function pairSort(a, b) {
return a.x - b.x;
}
var y = 0;
var check = [];
while (check.length < 100) {
check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));
}
check.sort(pairSort);
var min = {};
var issues = 0;
for (var i = 0; i < check.length; ++i) {
var entry = check[i];
var found = min[entry.x];
if (found) {
if (found.y > entry.y) {
console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);
++issues;
}
} else {
min[entry.x] = {x: entry.x, y: entry.y, i: i};
}
}
if (!issues) {
console.log("Sort appears to be stable");
}[,,,1,2,3].sort(()=>0) получил [3,2,1 ,,,]
- person martian; 17.06.2019
Я хотел бы поделиться трюком, который я обычно использую в 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;
});
После sort () второй массив будет содержать индексы, которые вы можете использовать для доступа к элементам исходного массива в стабильном отсортированном порядке.
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;
}
В общем, стабильные алгоритмы сортировки только созревают и по-прежнему требуют больше дополнительной памяти по сравнению со старым добрым qsort. Думаю, именно поэтому очень немногие спецификации требуют стабильной сортировки.
Начиная с версии V8 v7.0 и Chrome 70, наша Array.prototype.sort реализация теперь стабильна. ????
Раньше V8 использовал нестабильный QuickSort для массивов с другими чем 10 элементов. Теперь V8 использует стабильный алгоритм TimSort.
Единственный крупный движок JavaScript, который все еще имеет нестабильную Array#sort реализацию, - это Chakra, используемый в Microsoft Edge. Chakra использует QuickSort для массивов с другими чем 512 элементов. Для меньших массивов используется стабильная реализация сортировки вставкой.
Демо: https://mathiasbynens.be/demo/sort-stability
На случай, если кто-то сочтет это полезным, у меня для этого был полифилл, который я сейчас удаляю:
const stable = (count => {
const
array = new Array(count),
buckets = {};
let i, k, v;
for (i = 0; i < count; ++i) {
array[i] = [Math.floor(Math.random() * 3) + 1, i + 1]; // [1..3, 1..count]
}
array.sort((a, b) => a[0] - b[0]);
for (i = 0; i < count; ++i) {
[k, v] = array[i];
if (buckets[k] > v) {
return false;
}
buckets[k] = v;
}
return true;
// Edge's JS engine has a threshold of 512 before it goes unstable, so use a number beyond that:
})(600);
if (!stable) {
const
{ prototype } = Array,
{ sort } = prototype;
Object.defineProperty(prototype, 'sort', {
configurable : true,
value(sortFn) {
const
array = this,
len = array.length,
temp = new Array(len);
let i;
for (i = len; i-- > 0; /* empty */) {
temp[i] = i;
}
sortFn = sortFn || defaultSort;
sort.call(temp, (index1, index2) => sortFn(array[index1], array[index2]) || index1 - index2);
// we cannot do this directly into array since we may overwrite an element before putting it into the
// correct spot:
for (i = len; i-- > 0; /* empty */) {
temp[i] = array[temp[i]];
}
for (i = len; i-- > 0; /* empty */) {
array[i] = temp[i];
}
return array;
}
});
}Если вы ищете список браузеров, в которых вам следует использовать неродной алгоритм сортировки, я предлагаю не использовать.
Вместо этого выполняйте проверку работоспособности сортировки при загрузке скрипта и принимайте решение на основе этого.
Поскольку спецификация не требует определенного поведения в этом отношении, она не застрахована от последующих изменений, даже в той же строке браузера.
Вы можете отправить патч на http://www.browserscope.org/, чтобы включить такие тесты в их набор . Но опять же, обнаружение функций превосходит обнаружение браузером.
