Двадцатая и последняя часть серии тем по JavaScript, интерпретирующая исходный код сортировки v8.
предисловие
v8 — это движок JavaScript Chrome, а сортировка массивов полностью реализована в JavaScript.
Алгоритм сортировки зависит от длины массива: если длина массива меньше или равна 10, используется сортировка вставками, а если длина больше 10, используется быстрая сортировка. (Конечно, это утверждение не является строгим).
Давайте сначала рассмотрим сортировку вставками и быструю сортировку.
Сортировка вставками
принцип
Первый элемент рассматривается как упорядоченная последовательность, пересекает массив, а затем последовательно вставляет эту построенную заказанную последовательность.
значок
выполнить
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var element = arr[i];
for (var j = i - 1; j >= 0; j--) {
var tmp = arr[j];
var order = tmp - element;
if (order > 0) {
arr[j + 1] = tmp;
} else {
break;
}
}
arr[j + 1] = element;
}
return arr;
}
var arr = [6, 5, 4, 3, 2, 1];
console.log(insertionSort(arr));временная сложность
Временная сложность относится к вычислительной нагрузке, необходимой для выполнения алгоритма.Он исследует ситуацию, когда размер входного значения приближается к бесконечности.В общем случае количество повторений основных операций в алгоритме является функцией размера задачиn.
Лучший случай: массив в порядке возрастания, временная сложность: O(n)
В худшем случае: массив в порядке убывания, временная сложность: O(n²)
стабильность
Стабильность относится к тому, сохраняют ли те же элементы относительное положение после сортировки.
Следует отметить, что для неустойчивого алгоритма сортировки, пока приводится пример, его нестабильность можно объяснить, тогда как для устойчивого алгоритма сортировки алгоритм необходимо анализировать для получения устойчивых характеристик.
Например [3, 3, 1], после сортировки это все еще [3, 3, 1], но на самом деле вторая 3 стоит перед первой 3, так что это нестабильный алгоритм сортировки.
Сортировка вставками является стабильным алгоритмом.
Преимущество
Сортировка вставками более эффективна, когда массив должен быть отсортирован или когда размер задачи невелик. Вот почему v8 использует сортировку вставками, когда длина массива меньше или равна 10.
быстрая сортировка
принцип
- Выберите элемент как «датум»
- Элементы меньше «базы» перемещаются слева от «базы», элементы больше «базы» перемещаются справа от «базы».
- Для двух подмножеств слева и справа от «базы» повторяйте первый и второй шаги, пока во всех подмножествах не останется только один элемент.
Пример
Пример и следующая реализация взяты от учителя Руана Ифэна.Javascript-реализация быстрой сортировки (Quicksort)
Возьмем в качестве примера массив [85, 24, 63, 45, 17, 31, 96, 50]:
На первом этапе средний элемент 45 выбирается в качестве «базовой линии». (Эталонное значение может быть выбрано произвольно, но легче понять выбор промежуточного значения.)
Второй шаг по порядку сравнивает каждый элемент с «базовым уровнем», чтобы сформировать два подмножества, одно «меньше 45», а другое «больше или равно 45».
Третий шаг — повторить первый и второй шаги для двух подмножеств, пока во всех подмножествах не останется только один элемент.
выполнить
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
// 取数组的中间元素作为基准
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};Однако эта реализация требует дополнительного места для хранения левого и правого подмножеств, поэтому существует также реализация упорядочения на месте.
значок
Давайте посмотрим на схему реализации сортировки на месте:
Чтобы все поняли принцип быстрой сортировки, я замедлил скорость выполнения.
На этой диаграмме правило значения эталона состоит в том, чтобы взять крайний левый элемент, желтый цвет представляет текущий эталон, зеленый представляет элемент меньше эталона, а фиолетовый представляет элемент больше эталона.
Мы обнаружим, что зеленый элемент будет находиться непосредственно справа от базы, фиолетовый элемент будет перемещен назад, а затем данные и последний элемент зеленого цвета будут заменены местами. правильное положение, то есть предыдущие элементы меньше базового значения, все последующие элементы больше базового значения. Затем возьмите ориентиры для предыдущего и последующего элементов и отсортируйте их.
реализация на месте
function quickSort(arr) {
// 交换元素
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(arr, left, right) {
var pivot = arr[left];
var storeIndex = left;
for (var i = left + 1; i <= right; i++) {
if (arr[i] < pivot) {
swap(arr, ++storeIndex, i);
}
}
swap(arr, left, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left < right) {
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort(6, 7, 3, 4, 1, 5, 9, 2, 8))стабильность
Быстрая сортировка — нестабильная сортировка. Если вы хотите доказать, что порядок нестабилен, вам достаточно привести пример.
Итак, давайте возьмем один~
Возьмем в качестве примера массив [1, 2, 3, 3, 4, 5], поскольку выбор эталона неопределенный, если в качестве эталона выбран третий элемент (то есть первые 3), то все элементы меньше чем 3 Впереди те, которые больше или равны 3, находятся сзади, и нет проблем с отсортированным результатом. Но если выбран четвертый элемент (то есть вторые 3), элемент меньше 3 находится перед эталоном, а тот, что больше или равен 3, находится позади эталона, то первые 3 будут перемещены в позади второго 3, поэтому быстрая сортировка является нестабильной сортировкой.
временная сложность
В реализации Ruan Yifeng тест берет средний элемент, а тест берет самый левый элемент в сортировке In-Situ. Основная точка быстрой сортировки - это выбор ориентиров. Когда выбираются разные тесты, будут разные выступления.
Временная сложность быстрой сортировки предпочтительно равна O(nlogn), но почему именно nlogn? Вот неточное доказательство:
В лучшем случае весь массив каждый раз делится поровну. Предполагая, что массив состоит из n элементов, глубина рекурсии равна log2n + 1, временная сложность O(n)[(log2n + 1)], поскольку временная сложность исследует ситуацию, когда размер входного значения приближается к бесконечности, младшие члены игнорируются, а временная сложность равна: o(nlog2н).
Если время выполнения программы является логарифмическим, программа будет постепенно замедляться по мере увеличения n. Если основание равно 10, lg1000 равно 3, а если n равно 1 000 000, lgn равно 6, всего в два раза больше. Если основание равно 2, запишите2Значение 1000 составляет около 10, log2Значение 1000000 составляет около 19, что примерно в два раза больше. Мы можем обнаружить, что логарифмическая функция любого основания на самом деле отличается постоянным кратным. Таким образом, мы думаем, что O(logn) уже может выражать логарифм всех оснований, поэтому временная сложность, наконец, равна: O(nlogn).
В худшем случае, если для отсортированного массива всегда выбирается первый элемент или последний элемент каждый раз, когда выбирается ссылочный элемент, то каждый раз будет пустое подмножество, и количество рекурсивных уровней достигнет n, и наконец, временная сложность алгоритма вырождается до O (n²).
Это также полностью показывает, насколько важен выбор бенчмарка, и в версии 8 сделано множество оптимизаций выбора бенчмарков для повышения производительности.
выбор бенчмарка v8
Принцип бенчмарка выбора v8 заключается в том, чтобы выбрать по одному элементу в начале и в конце, а затем отсортировать три значения, чтобы взять среднее значение.
Когда длина массива больше 10, но меньше 1000, возьмите элемент в средней позиции, код реализации:
// 基准的下标
// >> 1 相当于除以 2 (忽略余数)
third_index = from + ((to - from) >> 1);Когда длина массива больше 1000, возьмите значение каждые 200 ~ 215 элементов, затем отсортируйте эти значения и возьмите нижний индекс среднего значения.Реализованный код:
// 简单处理过
function GetThirdIndex(a, from, to) {
var t_array = new Array();
// & 位运算符
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
// 对随机挑选的这些值进行排序
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
// 取中间值的下标
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}Может быть, вам будет любопытно200 + ((to - from) & 15)Что значит?
&Представляет побитовое И, побитовое выполнение логической операции И над целочисленными операндами. Этот бит в результате равен 1, только если соответствующие биты в обоих операндах равны 1.
к15 & 127Например:
15 в двоичном формате: (0000 1111)
127 в двоичном формате: (1111 1111)
Результат побитового И: (0000 1111) = 15
так15 & 127Результат15.
Обратите внимание, что двоичное число 15:1111, что означает, что результат любого побитового И 15 будет меньше или равен 15, что реализует значение через каждые 200–215 элементов.
исходный код v8
Наконец-то пришло время взглянуть на исходный код! Адрес источника:GitHub.com/V8/V8/blob/….
function InsertionSort(a, from, to) {
for (var i = from + 1; i < to; i++) {
var element = a[i];
for (var j = i - 1; j >= from; j--) {
var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
};
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;
}
}
}
var arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
function comparefn(a, b) {
return a - b
}
QuickSort(arr, 0, arr.length)
console.log(arr)Начнем с массива[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]В качестве примера проанализируйте процесс исполнения.
1. Выполните функцию QuickSort.Значение параметра from равно 0, а значение параметра to равно 11.
2.10 (0 + 11 >> 1) = 5, эталонное значение a[5] равно 5.
3. Сравните значения a[0] a[10] a[5], а затем измените массив в соответствии с результатом сравнения, массив равен [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
4. Поменять опорное значение местами с (с + 1)-м элементом массива, то есть со вторым элементом массива.В это время массив равен [0, 5, 8, 7, 6, 9, 4 , 3, 2, 1, 10], элемент перед эталонным значением 5 в это время должен быть меньше 5, поскольку на третьем шаге было выполнено сравнение. Последующие элементы не сортируются.
Все, что нам нужно сделать дальше, это переместить все следующие элементы, которые меньше 5, в начало 5.
5. Далее входим в цикл разбиения, этот массив еще берем для примера, извлекаем отдельно и пишем демку, чтобы рассказать о ней
// 假设代码执行到这里，为了方便演示，我们直接设置 low_end 等变量的值
// 可以直接复制到浏览器中查看数组变换效果
var a = [0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10]
var low_end = 1;
var high_start = 10;
var pivot = 5;
console.log('起始数组为', a)
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
console.log('循环当前的元素为：', a[i])
var order = element - pivot;
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
console.log(a)
}
else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = top_elem - pivot;
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
console.log(a)
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
console.log(a)
}
}
console.log('最后的结果为', a)
console.log(low_end)
console.log(high_start)6. В этот момент массив[0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10], цикл начинается с третьего элемента, значение a[i] равно 8, потому что оно больше эталонного значения 5, то есть порядок > 0, запуск цикла do while, цель цикла do while заключается в поиске элементов в обратном порядке и поиске первого элемента меньшего, чем элемент базового значения, а затем обмене этого элемента с позицией a[i].
Первый элемент меньше базового значения равен 1, затем 1 заменяется на 8, и массив становится[0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]. Значение high_start должно записывать, где находится обратный порядок.
7. В это время значение a[i] становится равным 1, а затем 1 заменяется эталонным значением 5, и массив становится[0, 1, 5, 7, 6, 9, 4, 3, 2, 8, 10], значение low_end увеличивается на 1, а значение low_end предназначено для записи местоположения эталонного значения.
8. Затем выполняется цикл, обходящий четвертый элемент 7, что согласуется с шагами 6 и 7, и массив сначала становится[0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10], затем становится[0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10]
9. Обходя пятый элемент 6, на шестом и седьмом шагах массив совпадает с первым[0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10], затем становится[0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]
10. Проходим шестой элемент 9, в соответствии с шагами 6 и 7 массив сначала становится[0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10], затем становится[0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10]
11. При следующем обходе, поскольку i == high_start, это означает, что поиск в положительном и обратном порядке, наконец, найден вместе, и следующие элементы определенно больше эталонного значения, и в это время цикл завершается.
12. Результат после обхода[0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10], все элементы перед ссылочным значением 5 меньше 5, а все элементы позади больше 5, а затем мы выполняем быструю сортировку для двух подмножеств соответственно
13. В это время значение low_end равно 5, значение high_start равно 6, значение to по-прежнему равно 10, а значение from по-прежнему равно 0.to - high_start < low_end - fromРезультатtrue, мы сортируем QuickSort(a, 6, 10), то есть сортируем следующие элементы, но учтите, что в новом QuickSort, поскольку значение from-to меньше 10, на этот раз фактически используется сортировка вставками. Итак, если быть точным,Когда длина массива превышает 10, v8 использует гибридный метод быстрой сортировки и сортировки вставками.
14. Тогдаto = low_endТо есть установить на 5, потому что while(true) будет выполняться снова, значение to - from равно 5, и выполняется InsertionSort(a, 0, 5), то есть выполняется сортировка вставками на элементах перед ссылочным значением.
15. Поскольку в решении to - from
16.v8 После выполнения быстрой сортировки массива, а затем выполнения сортировки вставками для двух подмножеств соответственно массив окончательно преобразуется в правильно отсортированный массив.
Сравнивать
Наконец, давайте возьмем схематическую диаграмму, чтобы почувствовать сортировку вставками и быструю сортировку:
картинка изwoohoo.topthem.com/developers/…
Тематическая серия
Адрес каталога серии тем JavaScript:GitHub.com/ в настоящее время имеет бриз….
Ожидается, что в серии тем JavaScript будет написано около 20 статей, в основном для изучения реализации некоторых функциональных точек в ежедневной разработке, таких как защита от сотрясений, регулирование, дедупликация, оценка типов, копирование, максимальное значение, плоское, карри, рекурсия, беспорядок. , сортировка и т. д., характеризуется поиском (чао), исследованием (кси), реализацией подчеркивания и jQuery.
Если есть какие-либо ошибки или неточности, пожалуйста, поправьте меня, большое спасибо. Если вам нравится или у вас есть вдохновение, добро пожаловать в звезду, что также является поощрением для автора.