Реализация Javascript Array.sort?
Какой алгоритм делает JavaScript Array#sort() использование функции? Я понимаю, что для выполнения разных видов сортировки могут потребоваться всевозможные аргументы и функции, меня просто интересует, какой алгоритм использует сортировка ванили.
7 ответов
Если вы посмотрите на эту ошибку 224128, похоже, что MergeSort используется Mozilla.
Я только что посмотрел на источник WebKit (Chrome, Safari...). В зависимости от типа массива используются разные методы сортировки:
Числовые массивы (или массивы примитивного типа) сортируются с использованием стандартной библиотечной функции C++ std::qsort который реализует некоторую вариацию быстрой сортировки (обычно интросорт).
Смежные массивы нечислового типа подвергаются строковому форматированию и сортируются с использованием mergesort, если доступно (для получения стабильной сортировки) или qsort если сортировка слиянием недоступна.
Для других типов (несмежных массивов и, предположительно, для ассоциативных массивов) WebKit использует либо сортировку выбора (которую они называют "минимальной" сортировкой), либо, в некоторых случаях, сортировку через дерево AVL. К сожалению, документация здесь довольно расплывчата, поэтому вам придется проследить пути кода, чтобы фактически увидеть, для каких типов используется метод сортировки.
И затем есть драгоценные камни как этот комментарий:
// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).
- Будем просто надеяться, что тот, кто на самом деле "исправит" это, лучше понимает асимптотическую среду выполнения, чем автор этого комментария, и понимает, что сортировка по основанию имеет немного более сложное описание среды выполнения, чем просто O (N).
(Спасибо phsource за указание на ошибку в исходном ответе.)
Для JS не существует чернового требования использовать определенный алгоритм сортировки. Как уже упоминалось здесь, Mozilla использует сортировку слиянием. Однако в исходном коде Chrome v8 на сегодняшний день он использует QuickSort и InsertionSort для небольших массивов.
Из строк 807 - 891
var QuickSort = function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from = high_start;
}
}
};
Стандарт ECMAscript не определяет, какой алгоритм сортировки должен использоваться. Действительно, разные браузеры имеют разные алгоритмы сортировки. Например, метод sort() в Mozilla / Firefox нестабилен (в смысле сортировки слова) при сортировке карты. Сортировка IE () стабильна.
Начиная с V8 v7.0 / Chrome 70, V8 использует TimSort, алгоритм сортировки Python. Chrome 70 был выпущен 13 сентября 2018 года.
См. Сообщение в блоге разработчика V8 для получения подробной информации об этом изменении. Вы также можете прочитать исходный код или патч 1186801.
После еще нескольких исследований для Mozilla/Firefox оказалось, что Array.sort() использует mergesort. Смотрите код здесь.
Я думаю, что это будет зависеть от того, какую реализацию браузера вы используете.
Каждый тип браузера имеет свою собственную реализацию движка javascript, так что это зависит. Вы можете проверить репозитории исходного кода для Mozilla и Webkit/Khtml для различных реализаций.
IE, однако, является закрытым исходным кодом, поэтому вам, возможно, придется спросить кого-то в Microsoft
Попробуйте это с быстрой сортировкой:
function sort(arr, compareFn = (a, b) => a <= b) {
if (!arr instanceof Array || arr.length === 0) {
return arr;
}
if (typeof compareFn !== 'function') {
throw new Error('compareFn is not a function!');
}
const partition = (arr, low, high) => {
const pivot = arr[low];
while (low < high) {
while (low < high && compareFn(pivot, arr[high])) {
--high;
}
arr[low] = arr[high];
while (low < high && compareFn(arr[low], pivot)) {
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
};
const quickSort = (arr, low, high) => {
if (low < high) {
let pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
return arr;
};
return quickSort(arr, 0, arr.length - 1);
}
Функция JavaScript Array.sort() имеет внутренние механизмы для выбора лучшего алгоритма сортировки ( QuickSort, MergeSort и т. Д.) На основе типа данных элементов массива.