В последние несколько дней я систематически просматривал алгоритм сортировки, и я не изучал его систематически раньше и не оставлял никаких заметок, поэтому быстро забыл его, на этот раз я изучу его внимательно.
Прежде всего, чтобы уменьшить ограничения, следующий код работает на движке Node V8 вместо браузера.Исходный код находится вмой GitHub, если вам интересно, вы можете скачать его и попробовать.
Чтобы облегчить сравнение производительности различных алгоритмов сортировки, вот метод создания крупномасштабных массивов —generateArray:
exports.generateArray = function(length) {
let arr = Array(length);
for(let i=0; i<length; i++) {
arr[i] = Math.random();
}
return arr;
};
Просто введите длину массива, чтобы сгенерировать случайный массив, соответствующий требованиям длины.
1. Пузырьковая сортировка
Пузырьковая сортировка также известна как сортировка погружением.Пузырьковая сортировка получила свое название от своего метода сортировки.Он проходит через весь массив, сравнивает каждый элемент массива со следующим элементом, и если он не соответствует требованиям, меняет местами позиции и проходит всего n раундов, где n — длина массива. После n раундов массив полностью отсортирован. Элементы массива, которые соответствуют требованиям во всем процессе, доходят до конца массива, как пузырьки со дна воды на поверхность, поэтому такая сортировка называется пузырьковой сортировкой.
Пузырьковая сортировка — простейший метод сортировки, легкий для понимания и простой в реализации, но пузырьковая сортировка — наименее эффективный алгоритм сортировки. 2). В лучшем случае, учитывая отсортированный массив и пузырьковую сортировку, временная сложность также составляет O (n).
Отдельное спасибо за комментарии@ Снежный молитвенный танецоптимизации каждое всплытие игнорирует i элементов, которые были отсортированы в хвосте.
Реализация JavaScript (сортировка от меньшего к большему):
function bubbleSort(arr) {
//console.time('BubbleSort');
// 获取数组长度，以确定循环次数。
let len = arr.length;
// 遍历数组len次，以确保数组被完全排序。
for(let i=0; i<len; i++) {
// 遍历数组的前len-i项，忽略后面的i项（已排序部分）。
for(let j=0; j<len - 1 - i; j++) {
// 将每一项与后一项进行对比，不符合要求的就换位。
if(arr[j] > arr[j+1]) {
[arr[j+1], arr[j]] = [arr[j], arr[j+1]];
}
}
}
//console.timeEnd('BubbleSort');
return arr;
}
Код в закомментированной части кода используется для вывода времени сортировки для тестирования, и то же самое верно ниже.
Во-вторых, сортировка выбором
Сортировка выбором — это метод сортировки методом сравнения на месте, общая идея которого заключается в следующем:
Найдите наименьшее (наибольшее) значение в массиве и поместите его первым, затем найдите второе наименьшее значение и поместите его во второе... и так далее.
Реализация JavaScript (сортировка от меньшего к большему):
function selectionSort(arr) {
//console.time('SelectionSort');
// 获取数组长度，确保每一项都被排序。
let len = arr.length;
// 遍历数组的每一项。
for(let i=0; i<len; i++) {
// 从数组的当前项开始，因为左边部分的数组项已经被排序。
let min = i;
for(let j=i; j<len; j++) {
if(arr[j] < arr[min]) {
min = j;
}
}
if(min !== i) {
[arr[min], arr[i]] = [arr[i], arr[min]];
}
}
//console.timeEnd('SelectionSort');
return arr;
}
Поскольку два слоя циклов вложены друг в друга, временная сложность также составляет O (n ^ 2),
3. Сортировка вставками
Сортировка вставками ближе всего к жизни, потому что именно так мы и играем в покер. Этот метод перебирает массив, начиная со второго элемента массива.n-1Элемент (n — длина массива).В процессе обхода левые элементы массива текущего элемента сравниваются по очереди справа налево.Если левый параметр больше (или меньше) текущего элемента, левый вариант переместится вправо, а затем продолжит сравнение предыдущего элемента до тех пор, пока не будет найден вариант, который не больше (не меньше) самого себя, для всех вариантов больше текущего элемента один элемент перемещается в правильно, исходя из исходного положения.
Пример:
// 对于如下数组
var arr = [2,1,3,5,4,3];
// 从第二项（即arr[1]）开始遍历，
// 第一轮：
// a[0] >= 1为true，a[0]右移，
arr = [2,2,3,5,4,3];
// 然后1赋给a[0]，
arr = [1,2,3,5,4,3];
// 然后第二轮：
// a[1] >= 3不成立，该轮遍历结束。
// 第三轮;
// a[2] >= 5不成立，该轮遍历结束。
// 第四轮：
// a[3] >= 4为true，a[3]右移，
arr = [1,2,3,5,5,3];
// a[2] >= 4不成立，将4赋给a[3]，然后结束该轮遍历。
arr = [1,2,3,4,5,3];
// a[4] >= 3成立，a[4]右移一位，
arr = [1,2,3,4,5,5];
// arr[3] >= 3成立，arr[3]右移一位，
arr = [1,2,3,4,4,5];
// arr[2] >= 3成立，arr[2]右移一位，
arr = [1,2,3,3,4,5];
// arr[1] >= 3不成立，将3赋给a[2]，结束该轮。
arr = [1,2,3,3,4,5];
// 遍历完成，排序结束。
Если убрать знак равенства в сравнении, то можно уменьшить некоторые шаги, поэтому эта часть в коде JavaScript уменьшена, Реализация JavaScript (сортировка от меньшего к большему):
function insertionSort(arr) {
//console.time('InsertionSort');
let len = arr.length;
for(let i=1; i<len; i++) {
let j = i;
let tmp = arr[i];
while(j > 0 && arr[j-1] > tmp) {
arr[j] = arr[j-1];
j--;
}
arr[j] = tmp;
}
//console.timeEnd('InsertionSort');
return arr;
}
Сортировка вставками имеет худшую производительность, чем общие расширенные алгоритмы сортировки (быстрая сортировка, сортировка кучей), но все же имеет следующие преимущества:
- Он прост в реализации и не очень сложен для понимания.
- Эффективен для небольших наборов данных.
- Быстрее, чем другие алгоритмы сортировки (пузырьковая, выборка) со сложностью O(n^2). Это можно увидеть в тесте в конце статьи.
- Стабильный и своевременный...
В-четвертых, сортировка слиянием
На данный момент введено три метода сортировки, в том числе пузырьковая сортировка, сортировка выбором и сортировка вставками. Временная сложность этих трех методов сортировки составляет O (n ^ 2). Среди них пузырьковая сортировка проще всего реализуется и имеет наихудшую производительность. Сортировка выбором немного лучше, чем пузырьковая сортировка, но этого недостаточно. Сортировка вставками является одним из 3. Лучший исполнитель и более эффективен для небольших наборов данных. По этим причинам практичность трех не высока.Это самые основные и простые методы сортировки.Они в основном используются для обучения и их трудно использовать на практике.В этом разделе мы представим более продвинутые алгоритмы сортировки.
Сортировка слиянием — это первый алгоритм сортировки, который можно использовать на практике, производительность трех предыдущих недостаточно хороша, временная сложность сортировки слиянием составляет O(nlogn), что уже обусловлено предыдущими тремя алгоритмами.
Стоит отметить, что в JavaScriptArray.prototype.sortМетод не указывает, какой алгоритм сортировки использовать, что позволяет настраивать браузер, FireFox использует сортировку слиянием, а Chrome использует быструю сортировку.
Основная идея сортировки слиянием заключается вразделяй и властвуй, разделяй и властвуй — это идея решения исходного решения путем рекурсивного разложения проблемы на две или более подзадачи того же или родственного типа до тех пор, пока проблема не станет достаточно простой для решения, а затем объединения решений подзадач. проблемы.
Сортировка слиянием достигает цели синтеза решений подзадач, разбивая сложные массивы на достаточно маленькие массивы (содержащие только один элемент), а затем объединяя два отсортированных массива (массивы с одним элементом можно считать отсортированными массивами). Таким образом, суть сортировки слиянием заключается в том, как интегрировать два отсортированных массива, а разделение массива — это лишь вспомогательный процесс.
Пример:
// 假设有以下数组，对其进行归并排序使其按从小到大的顺序排列：
var arr = [8,7,6,5];
// 对其进行分解，得到两个数组：
[8,7]和[6,5]
// 然后继续进行分解，分别再得到两个数组，直到数组只包含一个元素：
[8]、[7]、[6]、[5]
// 开始合并数组，得到以下两个数组：
[7,8]和[5,6]
// 继续合并，得到
[5,6,7,8]
// 排序完成
Реализация JavaScript (сортировка от меньшего к большему):
function mergeSort(arr) {
//console.time('MergeSort');
//let count = 0;
console.log(main(arr));
//console.timeEnd('MergeSort');
//return count;
// 主函数。
function main(arr) {
// 记得添加判断，防止无穷递归导致callstack溢出，此外也是将数组进行分解的终止条件。
if(arr.length === 1) return arr;
// 从中间开始分解，并构造左边数组和右边数组。
let mid = Math.floor(arr.length/2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
// 开始递归调用。
return merge(arguments.callee(left), arguments.callee(right));
}
// 数组的合并函数，left是左边的有序数组，right是右边的有序数组。
function merge(left, right) {
// il是左边数组的一个指针，rl是右边数组的一个指针。
let il = 0,
rl = 0,
result = [];
// 同时遍历左右两个数组，直到有一个指针超出范围。
while(il < left.length && rl < right.length) {
//count++;
// 左边数组的当前项如果小于右边数组的当前项，那么将左边数组的当前项推入result，反之亦然，同时将推入过的指针右移。
if(left[il] < right[rl]) {
result.push(left[il++]);
}
else {
result.push(right[rl++]);
}
}
// 记得要将未读完的数组的多余部分读到result。
return result.concat(left.slice(il)).concat(right.slice(rl));
}
}
Обратите внимание, что поскольку массив разбивается на множество подмассивов с одним элементом, функция слияния начинает слияние с массива из одного элемента.Когда количество элементов в объединенном массиве превышает 1, это упорядоченный массив и может по-прежнему использовать функцию слияния для слияния.
Производительность сортировки слиянием действительно достигла прикладного уровня, но ее все еще несколько недостаточно, потому что здесь функция слияния создает новый результирующий массив для хранения объединенного массива, что приводит к увеличению пространственной сложности. чтобы массив работал на месте.
Пять, быстрая сортировка
Быстрая сортировка была изобретена Тони Хоаром в 1959 г. Это наиболее часто используемая схема сортировки. При правильном использовании ее скорость может быть в два-три раза выше, чем у обычных алгоритмов, и можно сказать, что она в тысячи раз быстрее, чем пузырьковая сортировка. и выбор рода раз. Сложность быстрой сортировки составляет O(nlogn), и ее основная идея также разделяй и властвуй.Он рекурсивно разбивает большие массивы на маленькие массивы до тех пор, пока длина массива не станет равной 1, но отличие от сортировки слиянием заключается в том, что ее основное внимание уделяется разложение массива, а слияние Точкой сортировки является слияние массивов.
Основная идея:
Выберите опорную точку (стержень) в массиве, а затем для каждого элемента массива элементы, большие, чем опорный элемент, помещаются в правую часть массива, а элементы, меньшие, чем опорный элемент, размещаются на левой стороне, и элементы массива слева и справа могут образовать два новых массива (левый и правый), а затем продолжить разложение влево и вправо соответственно до тех пор, пока длина массива не станет равной 1, и, наконец, объединиться (на самом деле слияния нет, потому что он работает на основе исходного массива, но теоретически массив декомпозируется).
Основные шаги:
- (1) Сначала выберите средний элемент массива в качестве опорной точки.
- (2) Создайте левый и правый указатели слева и справа, левый указывает на первый элемент массива, правый указывает на последний элемент, затем перемещайте левый указатель до тех пор, пока его значение не будет меньше, чем точка поворота, а затем перемещайте правый указатель до тех пор, пока его значение не больше, чем пивот.
- (3) Если левый по-прежнему не больше правого, поменяйте местами значения левого и правого указателей (указатели не меняются местами), затем переместите левый указатель вправо, а правый указатель влево и продолжите цикл до тех пор, пока левое значение больше, чем правое, и вернуть значение левого указателя.
- (4) В соответствии с результатом предыдущего раунда декомпозиции (значением левого) разрезать массив, чтобы получить два массива левых и правых, а затем разложить их соответственно.
- (5) Повторяйте описанный выше процесс, пока длина массива не станет равной 1, а затем завершите разложение.
Реализация JavaScript (сортировка от меньшего к большему):
function quickSort(arr) {
let left = 0,
right = arr.length - 1;
//console.time('QuickSort');
main(arr, left, right);
//console.timeEnd('QuickSort');
return arr;
function main(arr, left, right) {
// 递归结束的条件，直到数组只包含一个元素。
if(arr.length === 1) {
// 由于是直接修改arr，所以不用返回值。
return;
}
// 获取left指针，准备下一轮分解。
let index = partition(arr, left, right);
if(left < index - 1) {
// 继续分解左边数组。
main(arr, left, index - 1);
}
if(index < right) {
// 分解右边数组。
main(arr, index, right);
}
}
// 数组分解函数。
function partition(arr, left, right) {
// 选取中间项为参考点。
let pivot = arr[Math.floor((left + right) / 2)];
// 循环直到left > right。
while(left <= right) {
// 持续右移左指针直到其值不小于pivot。
while(arr[left] < pivot) {
left++;
}
// 持续左移右指针直到其值不大于pivot。
while(arr[right] > pivot) {
right--;
}
// 此时左指针的值不小于pivot，右指针的值不大于pivot。
// 如果left仍然不大于right。
if(left <= right) {
// 交换两者的值，使得不大于pivot的值在其左侧，不小于pivot的值在其右侧。
[arr[left], arr[right]] = [arr[right], arr[left]];
// 左指针右移，右指针左移准备开始下一轮，防止arr[left]和arr[right]都等于pivot然后导致死循环。
left++;
right--;
}
}
// 返回左指针作为下一轮分解的依据。
return left;
}
}
По сравнению с сортировкой слиянием, быстрая сортировка усиливает логику части декомпозиции, устраняет работу по объединению массивов и не требует выделения новой памяти для хранения результатов слияния массивов, поэтому она имеет лучшую производительность и в настоящее время является наиболее часто используемой. используемая схема сортировки.
Я видел ответ на Zhihu раньше Код примерно выглядит следующим образом (отсортировано от меньшего к большему):
function quickSort(arr) {
// 当数组长度不大于1时，返回结果，防止callstack溢出。
if(arr.length <= 1) return arr;
return [
// 递归调用quickSort，通过Array.prototype.filter方法过滤小于arr[0]的值，注意去掉了arr[0]以防止出现死循环。
...quickSort(arr.slice(1).filter(item => item < arr[0])),
arr[0],
...quickSort(arr.slice(1).filter(item => item >= arr[0]))
];
}
Приведенный выше код способствует пониманию идеи быстрой сортировки, но фактический эффект применения не очень хорош, и скорость предыдущего кода не такая высокая.
6. Куча сортировки
Если быстрая сортировка — наиболее применимый алгоритм сортировки, то я думаю, что кучевая сортировка — самый интересный метод сортировки, что очень интересно.
Сортировка кучей также является очень эффективным методом сортировки, потому что она названа в честь того, что массив отсортирован как двоичное дерево. Это можно рассматривать как улучшение сортировки слиянием. Это метод сортировки на месте, но он недостаточно стабилен. , а его временная сложность равна O (nlogn).
Этапы реализации:
- (1) Создайте структуру кучи из массива, которая удовлетворяет тому, что родительский узел всегда больше (или меньше) своего дочернего узла.
- (2) Начиная с крайнего правого листового узла структуры кучи, производить обмен с корневым узлом последовательно справа налево и снизу вверх.После каждого обмена снова строить структуру кучи. Стоит отметить, что каждый раз, когда создается структура кучи, некорневые узлы, которые были заменены, игнорируются.
Структура кучи, построенная массивом:
// 数组
var arr = [1,2,3,4,5,6,7];
// 堆结构
1
/ \
2 3
/ \ / \
4 5 6 7
Можно найти, что для индекса массива какiЭлемент массива , значение его левого дочернего элемента является индексом2*i + 1Соответствующий элемент массива, значение правого дочернего узла является индексом2*i + 2соответствующий элемент массива.
Фактически, он не освобождает место в памяти для построения структуры кучи для хранения данных массива, а логически обрабатывает массив как двоичное дерево Построение структуры кучи означает, что дочерние узлы любого родительского узла не больше ( не менее) родительского узла.
Реализация JavaScript (сортировка от меньшего к большему):
function heapSort(arr) {
//console.time('HeapSort');
buildHeap(arr);
for(let i=arr.length-1; i>0; i--) {
// 从最右侧的叶子节点开始，依次与根节点的值交换。
[arr[i], arr[0]] = [arr[0], arr[i]];
// 每次交换之后都要重新构建堆结构，记得传入i限制范围，防止已经交换的值仍然被重新构建。
heapify(arr, i, 0);
}
//console.timeEnd('HeapSort');
return arr;
function buildHeap(arr) {
// 可以观察到中间下标对应最右边叶子节点的父节点。
let mid = Math.floor(arr.length / 2);
for(let i=mid; i>=0; i--) {
// 将整个数组构建成堆结构以便初始化。
heapify(arr, arr.length, i);
}
return arr;
}
// 从i节点开始下标在heapSize内进行堆结构构建的函数。
function heapify(arr, heapSize, i) {
// 左子节点下标。
let left = 2 * i + 1,
// 右子节点下标。
right = 2 * i + 2,
// 假设当前父节点满足要求（比子节点都大）。
largest = i;
// 如果左子节点在heapSize内，并且值大于其父节点，那么left赋给largest。
if(left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点在heapSize内，并且值大于其父节点，那么right赋给largest。
if(right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if(largest !== i) {
// 如果largest被修改了，那么交换两者的值使得构造成一个合格的堆结构。
[arr[largest], arr[i]] = [arr[i], arr[largest]];
// 递归调用自身，将节点i所有的子节点都构建成堆结构。
arguments.callee(arr, heapSize, largest);
}
return arr;
}
}
Heapsort немного менее эффективен, чем quicksort, но это действительно интересно.
Семь, сравнение производительности
пройти черезconsole.time()иconsole.timeEnd()Чтобы узнать, сколько времени ушло на сортировку, перейдитеgenerateArray()Сгенерируйте крупномасштабные данные и, наконец, сделайте следующие выводы:
через паруПузырьковая сортировкаВ результате теста получены следующие данные:
BubbleSort: 406.567ms
Сортировка 10 000 (десяти тысяч) фрагментов данных занимает 406 миллисекунд.
BubbleSort: 1665.196ms
Сортировка 20 000 (20 000) фрагментов данных занимает 1,6 с.
BubbleSort: 18946.897ms
Сортировка 50 000 (50 000) фрагментов данных занимает 19 секунд. Поскольку машина не очень хорошая, когда объем данных достигает 100 000, это в основном очень долго, и она не ждала долго.Видно, что производительность очень плохая.
через парусортировка выборомВ результате теста получены следующие данные:
SelectionSort: 1917.083ms
Сортировка 20 000 (20 000) фрагментов данных занимает 1,9 с.
SelectionSort: 12233.060ms
При сортировке 50 000 (50 000) фрагментов данных потребовалось 12,2 с.Видно, что прогресс по сравнению с пузырьковой сортировкой есть, но далеко не достаточный. Также видно, что по мере увеличения объема данных затраты времени на сортировку становятся все больше и больше.
через паруСортировка вставкамиВ результате теста получены следующие данные:
InsertionSort: 273.891ms
Сортировать 200 000 (20 000) полос, много времени, потребляющие 0,27 с.
InsertionSort: 1500.631ms
Сортировка 50 000 (50 000) фрагментов данных занимает 1,5 с.
InsertionSort: 7467.029ms
Сортировка 100 000 (100 000) фрагментов данных занимает 7,5 секунд.По сравнению с сортировкой выбором, это большое улучшение, но этого все же недостаточно.
через паруСортировка слияниемВ результате теста получены следующие данные:
MergeSort: 287.361ms
Сортировка 100 000 (100 000) фрагментов данных занимает 0,3 секунды, что действительно отлично, ххх,
MergeSort: 2354.007ms
Сортировка 100 000 (1 миллион) данных, занимает 2,4 секунды, абсолютно отлично, неудивительно, что Firefox будет использовать это для определенияArray.prototype.sortметод,
MergeSort: 26220.459ms
Сортировка 10 000 000 (десяти миллионов) фрагментов данных занимает 26 секунд, что неплохо. Проверьте быструю сортировку дальше.
через парубыстрая сортировкаВ результате теста получены следующие данные:
QuickSort: 51.446ms
Для сортировки 100 000 (100 000) фрагментов данных требуется 0,05 с, что незначительно.
QuickSort: 463.528ms
Сортировка 1 000 000 (одного миллиона) фрагментов данных занимает 0,46 с, что в принципе незначительно.
QuickSort: 5181.508ms
Для сортировки 10 000 000 (десяти миллионов) фрагментов данных требуется 5,2 с, что вполне приемлемо.
через парусортировка кучейВ результате теста получены следующие данные:
HeapSort: 3124.188ms
Сортировка 1 000 000 (одного миллиона) фрагментов данных занимает 3,1 с, что уступает быстрой сортировке и сортировке слиянием, но все же хорошо по сравнению с другими методами сортировки.
HeapSort: 41746.788ms
Сортировка 10 000 000 (десяти миллионов) фрагментов данных занимает 41,7 с, что неприемлемо.
8. Заключение
Раньше я думал, что метод сортировки можно использовать случайно. Теперь я думаю об этом, ххх, это действительно наивно. Я помню, что когда я практиковался, SQL Server сортировал миллионы данных за несколько секунд. Черные глаза? Благодаря этому изучению и краткому изложению алгоритмов сортировки, особенно для проверки производительности каждого метода, я глубоко осознал важность разработки алгоритма. Только обращая внимание на сравнение конструкции и сложности алгоритма, мы можем писать отличные алгоритмы. Алгоритмы могут создавать приложения с превосходное представление!
Кроме того, так как исследование сложности алгоритма недостаточно глубокое, понимание только на поверхности, так что если есть ошибки в тексте, прошу меня просветить!
Наконец, я хотел бы сказать, что я поддерживаю Учителя Жуана!