предисловие
Как говорится, золото — это три серебра, четыре золота — это девять, а серебро — десять, и это снова золотой сезон смены работы. Тем не менее, в этом году конкуренция за передовые позиции будет более интенсивной, чем когда-либо.
В сегодняшнем процессе собеседования алгоритм — это элемент знаний, который часто изучается, а сортировка — относительно основная часть алгоритма.Не так уж сложно попросить интервьюера написать несколько алгоритмов сортировки на месте.
Итак, в последнее время десять общих алгоритмов сортировки сортируются следующим образом, а также некоторые общие методы оптимизации и некоторый соответствующий leetcode (портал) тему, предлагаю подать заявку на аккаунт, чтобы освежить его.Ведь понимать его и уметь писать и проходить все кейсы в LeetCode это две разные вещи.Надеюсь,может помочь тем,кто новичок в алгоритмах и кому недавно нужно было участвовать в интервью.
Ведь у меня в руке еда, так что я не паникую (убегаю~
- В этой статье в основном объясняются следующие десять классических алгоритмов сортировки:
- Пузырьковая сортировка
- сортировка выбором
- Сортировка вставками
- Сортировка слиянием
- сортировка кучей
- быстрая сортировка
- сортировка ведром
- сортировка по основанию
- Сортировка холмов
- сортировка по подсчету
хочу увидеть исходный кодкликните сюда, читатель может клонировать и запустить его локально. Кстати, статья с исходным кодом еще лучше~~~
Наконец, если вы столкнетесь с проблемами во время чтения или у вас есть лучшие методы оптимизации, вы можете ограничиться личными возможностями:
- пришлите мне вопрос
- или пул-реквесты
- Комментарий под этим постом
Я увижу и разберусь с этим, добро пожаловать, Стар, ваша поддержка — самая большая мотивация для моего письма.
Подготовить
-
Стабильность алгоритма сортировки:Если взаимное расположение двух одинаковых чисел до и после сортировки остается неизменным, алгоритм устойчив.
-
временная сложность:Это просто понимается как время, необходимое для выполнения алгоритма, обычно используемоеОбозначение большого O, подробное объяснение см.временная сложность
-
Космическая сложность:Объем памяти, необходимый для запуска программы.
Сложность общих алгоритмов (Картинка взята из интернета)
/**
* 按照正序比较并交换数组中的两项
*
* @param {Array} ary
* @param {*} x
* @param {*} y
*/
function swap(ary, x, y) {
if (x === y) return
var temp = ary[x]
ary[x] = ary[y]
ary[y] = temp
}
Пузырьковая сортировка (Bubble-Sort)
Пузырьковая сортировкапростой алгоритм сортировки. Он неоднократно проходит через последовательность для сортировки, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Работа по посещению последовательности повторяется до тех пор, пока перестановки не понадобятся, то есть последовательность отсортирована. Название этого алгоритма происходит от того факта, что меньшие элементы медленно «вплавляются» в верхнюю часть последовательности путем замены.
Шаги алгоритма:Предположим, что в конечном итоге нам нужен упорядоченный массив, который последовательно увеличивается.
- Начиная с первой позиции массива, сравниваем размеры соседних элементов в обратном порядке, если первый меньше второго, то меняем местами две позиции до конца массива.
- Сравните следующую начальную позицию по одному, затем повторите первый шаг.
- Повторяйте 1~2, пока сортировка не закончится.
function bubbleSort1(ary) {
var l = ary.length
for (var i = 0; i < l-1; i++) {
for (var j = 0; j <= l-2; j++) {
if (ary[j] > ary[j + 1]) {
swap(ary, j, j + 1)
}
}
}
return ary
}
оптимизация: Приведенная выше сортировка требует n * n сортировок для сортировки массива длины n. (Количество циклов как для внутреннего, так и для внешнего слоев равно n ) Предвидится, что длина упорядоченной части от конца массива будет увеличиваться на единицу для каждого всплывающего раунда, а значит, операция сравнения упорядоченного массива в конце массива бесполезна.
Усовершенствованный алгоритм выглядит следующим образом:
function bubbleSort2(ary) {
var l = ary.length
for (var i = l - 1; i >= 0; i--) {
// 优化的部分 arr[i]及之后的部分都是有序的
for (var j = 0; j < i; j++) {
if (ary[j] > ary[j + 1]) {
swap(ary, j, j + 1)
}
}
}
return ary
}
Точка оптимизации: для обработки некоторых предельных случаев сравнения приведите пример предела сравнения, если данный массив уже является упорядоченным массивом, тогда пузырьковая сортировка1 и bubbleSort2 по-прежнему достаточно глуп, чтобы выполнить предопределенное количество раз n*n и n! соответственно. Конечно, с такой ситуацией столкнуться непросто, но с ней легко столкнуться в последней части сортировки. Теоретически та часть, которая должна быть несортированной, на самом деле уже в порядке. Нам нужно отфильтровать и разобраться с этой ситуацией. . Введите swapedFlag , Если внутренний цикл не был введен на предыдущем шаге сортировки, это означает, что остальные элементы в порядке и сортировка завершена.
Оптимизированный код выглядит следующим образом:
/**
* 冒泡排序 优化
*
* @param {Array} ary
* @returns
*/
function bubbleSort3(ary) {
var l = ary.length
var swapedFlag
for (var i = l - 1; i >= 0; i--) {
swapedFlag = false
for (var j = 0; j < i; j++) {
if (ary[j] > ary[j + 1]) {
swapedFlag = true
swap(ary, j, j + 1)
}
}
if (!swapedFlag) {
break
}
}
return ary
}
Сортировка выбором (сортировка выбором)
сортировка выборомОн заключается в том, чтобы сначала найти наибольший или наименьший элемент в данных и поместить его в начало последовательности, затем продолжить поиск наибольшего или наименьшего элемента из оставшихся данных и по очереди поместить его в сортирующую последовательность, пока не будут получены все данные. образцы сортируются.Анализ сложности: Очевидно, что сортировка выбором также является трудоемким алгоритмом сортировки, независимо от того, какие данные, он требует временной сложности O(n*n), что не подходит для сортировки большого количества данных.
Шаги алгоритма:Неупорядоченная область (массив) с начальным состоянием n может быть выбрана напрямую и отсортирована n-1 раз для получения упорядоченного результата.
- Исходное состояние: неупорядоченная область R[0..n], упорядоченная область пуста;
- В начале i-й сортировки (i=0,1,2,3...n-1) текущей упорядоченной и неупорядоченной областью являются R[0..i] и R(i+1.. н) соответственно. Эта сортировка выбирает позицию записи с наименьшим ключевым словом (индекс minPos) из текущей неупорядоченной области и обменивает R[minPos] с первой записью R[i] неупорядоченной области, поэтому длина упорядоченной области добавляется. 1 Вычтите 1 из длины неупорядоченной области. Затем добавьте 1 к i и выполните следующую сортировку.
- Конец n-1 раз, сортировка массива завершена
function selectSort(ary) {
var l = ary.length
var minPos
for (var i = 0; i < l - 1; i++) {
minPos = i
for (var j = i + 1; j < l; j++) {
if (ary[j] - ary[minPos] < 0) {
minPos = j
}
}
swap(ary, i, minPos)
}
return ary
}
Сортировка вставками
Сортировка вставкамиСначала первый элемент сортируемой последовательности рассматривается как упорядоченная последовательность, а второй элемент до последнего элемента рассматривается как несортированная последовательность, затем несортированная последовательность просматривается от начала до конца, и каждый элемент просматривается. будет Вставлять соответствующую позицию отсортированной последовательности до тех пор, пока все данные не будут отсортированы; если вставляемый элемент равен элементу в отсортированной последовательности, вставляемый элемент вставляется после равного элемента.
Шаги алгоритма:
- Начиная с первого элемента, элемент можно считать отсортированным
- Возьмите следующий элемент и просканируйте его от начала до конца в отсортированной последовательности элементов.
- Если элемент (отсортированный) больше нового элемента, переместите элемент в следующую позицию
- Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
- После вставки нового элемента в эту позицию
- Повторите шаги 2–5.
function insertionSort1(arr) {
var l = arr.length;
var preIndex, current;
for (var i = 1; i < l; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
Идеи оптимизации:
- Дихотомия: то есть при вставке вновь добавленного значения в упорядоченный массив количество поисков уменьшается за счет дихотомии.
- Связанный список: преобразование упорядоченной части массива в структуру связанного списка, тогда временная сложность вставки становится O (1), а сложность поиска становится O (n) (поскольку неудобно использовать дихотомию)
- Отсортированное двоичное дерево (BST): преобразование упорядоченной части массива в структуру отсортированного двоичного дерева, а затем обход двоичного дерева по порядку. Использование отсортированного бинарного дерева может учитывать удобство вставки и эффективность поиска. Но занимает дополнительное место. Поэтому БСТ — это относительно сбалансированный способ мышления, а также воплощение идеи смены пространства временем.
Краткое введение в дихотомию:Двоичный поиск — это поисковый алгоритм для нахождения определенного элемента в упорядоченном массиве. Процесс поиска начинается со среднего элемента массива.Если средний элемент является именно тем элементом, который нужно найти, процесс поиска заканчивается, если конкретный элемент больше или меньше среднего элемента, он ищет в половине массива. массив, который больше или меньше среднего элемента. , и начинаем сравнение со среднего элемента, как в начале. Если на каком-то шаге массив пуст, значит, он не найден. Этот алгоритм поиска уменьшает диапазон поиска наполовину для каждого сравнения.
Примечание:Учащиеся, готовящиеся к собеседованию, могут понимать и запоминать одно из следующего: Реализация сортировки двоичных деревьев и связанных списков не будет подробно обсуждаться из-за нехватки места. Я представлю их подробно при подготовке к написанию структур данных позже. Эта статья вводит идею использования метода дихотомии для оптимизации разбиения на сортировку. :
/**
* 插入排序
*
* @param {*} ary
* @returns {Arrray} 排序完成的数组
*/
function insertSort2(ary) {
return ary.reduce(insert, [])
}
/**
* 使用二分法完成查找插值位置，并完成插值操作。
* 时间复杂度 logN
* @param {*} sortAry 有序数组部分
* @param {*} val
* @returns
*/
function insert(sortAry, val) {
var l = sortAry.length
if (l == 0) {
sortAry.push(val)
return sortAry
}
var i = 0,
j = l,
mid
//先判断是否为极端值
if (val < sortAry[i]) {
return sortAry.unshift(val), sortAry
}
if (val >= sortAry[l - 1]) {
return sortAry.push(val), sortAry
}
while (i < j) {
mid = ((j + i) / 2) | 0
//结束条件 等价于j - i ==1
if (i == mid) {
break
}
if (val < sortAry[mid]) {
j = mid
}
if (val == sortAry[mid]) {
i = mid
break
}
//结束条件 统一c处理对外输出i
if (val > sortAry[mid]) {
i = mid
}
}
var midArray = [val]
var lastArray = sortAry.slice(i + 1)
sortAry = sortAry
.slice(0, i + 1)
.concat(midArray)
.concat(lastArray)
return sortAry
}
Сортировка слиянием (Merge-Sort)
Сортировка слияниемЭто метод сортировки, реализованный идеей слияния.Алгоритм использует классическую стратегию «разделяй и властвуй» (метод «разделяй и властвуй» делит проблему на несколько небольших задач, а затем решает их рекурсивно, в то время как метод «властвуй»). этап «фиксирует» ответы, полученные на разделенных этапах вместе, то есть разделяй и властвуй).
Анализ стабильности: сортировка слиянием строго следует порядку слияния последовательностей подданных слева направо или справа налево, она не меняет относительный порядок между одними и теми же данными, поэтому сортировка слиянием является стабильным алгоритмом сортировки.
Шаги алгоритма:
- Разделить входную последовательность длины n на две подпоследовательности длины n/2;
- Сортировка слиянием используется для этих двух подпоследовательностей соответственно;
- Два сортированных подпоследовательности объединяются в последнюю последовательность сортировки.
// 采用自上而下的递归方法
function mergeSort(ary) {
if (ary.length < 2) {
return ary.slice()
}
var mid = Math.floor(ary.length / 2)
var left = mergeSort(ary.slice(0, mid))
var right = mergeSort(ary.slice(mid))
var result = []
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
result.push(...left, ...right)
return result
}
Heapsort
сортировка кучейЭто относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Структура стека имеет следующие характеристики: то есть значение ключа дочернего узла всегда меньше (или больше) его родительского узла, который можно разделить на следующие две категории:
- Максимальная куча: значение каждого узла больше или равно значению его дочерних узлов, используемых в алгоритме сортировки кучи по возрастанию;
- Минимальная куча: значение каждого узла меньше или равно значению его дочерних узлов, используемому в алгоритме сортировки кучи по убыванию;
Шаги алгоритма:
- Создать кучу H[0...n-1];
- Поменять местами голову кучи (максимальное значение) и хвост кучи;
- Размер кучи уменьшается на 1, и вызывается метод reheap для повторной кучи, цель которого — настроить верхние данные нового массива на соответствующую позицию и снова стать самой большой кучей.
/**
* 聚堆：将数组中的某一项作为堆顶，调整为最大堆。
* 把在堆顶位置的一个可能不是堆，但左右子树都是堆的树调整成堆。
*
* @param {*} ary 待排序数组
* @param {*} topIndex 当前处理的堆的堆顶
* @param {*} [endIndex=ary.length - 1] 数组的末尾边界
*/
function reheap(ary, topIndex, endIndex = ary.length - 1) {
if (topIndex > endIndex) {
return
}
var largestIndex = topIndex
var leftIndex = topIndex * 2 + 1
var rightIndex = topIndex * 2 + 2
if (leftIndex <= endIndex && ary[leftIndex] > ary[largestIndex]) {
largestIndex = leftIndex
}
if (rightIndex <= endIndex && ary[rightIndex] > ary[largestIndex]) {
largestIndex = rightIndex
}
if (largestIndex != topIndex) {
swap(ary, largestIndex, topIndex)
reheap(ary, largestIndex, endIndex)
}
}
/**
* 将数组调整为最大堆结构
*
* @param {*} ary
* @returns
*/
function heapify(ary) {
for (var i = ary.length - 1; i >= 0; i--) {
reheap(ary, i)
}
return ary
}
/**
* 堆排序
*
* @param {*} ary
* @returns
*/
function heapSort(ary) {
heapify(ary)
for (var i = ary.length - 1; i >= 1; i--) {
swap(ary, 0, i)
reheap(ary, 0, i - 1)
}
return ary
}
Быстрая сортировка
быстрая сортировкаИспользуйте стратегию «разделяй и властвуй», чтобы разделить массив на два подмассива. Сначала выберите элемент из массива и назовите этот элемент «эталоном», англ. Переупорядочите массив так, чтобы все элементы, меньшие базового значения, располагались перед основанием, а все элементы, превышающие базовое значение, размещались после основания (одно и то же число может идти с любой стороны). После того, как этот раздел заканчивается, данные находятся в середине массива. Это называется операцией разделения. После этого продолжайте повторять этот метод в подпоследовательностях, пока, наконец, не будет отсортирована вся последовательность данных.
Уведомление: Самая трудоемкая реализация быстрой сортировки в js — обмен, в этом примере элементы дозора получаются случайным образом, и первое значение в массиве всегда берется за точку опоры в приведенной выше анимации, далее рассмотрим предельный случай , в случае [9, 8, 7, 6, 5, 4, 3, 2, 1] сложность алгоритма станет n*n при использовании сортировки на месте. Дозорный в этом примере выбирается случайным образом из массива, и я лично считаю, что это лучше, чем брать первый элемент.
заявление:Возьмите первые K элементов, найдите медиану,leetcode
Что ж, начнем с грубой версии, чтобы понять основную идею быстрой сортировки:
//快排粗暴版本
function quickSort1(ary) {
if (ary.length < 2) {
return ary.slice()
}
var pivot = ary[Math.floor(Math.random() * ary.length)]
var left = []
var middle = []
var right = []
for (var i = 0; i < ary.length; i++) {
var val = ary[i]
if (val < pivot) {
left.push(val)
}
if (val === pivot) {
middle.push(val)
}
if (val > pivot) {
right.push(val)
}
}
return quickSort1(left).concat(middle, quickSort(right))
}
Это рекомендуется освоить.Очень важный(стучит по доске)
Шаг алгоритма
- Выберите элемент из последовательности, называемый «стержнем»;
- Измените порядок последовательности, все элементы, меньшие, чем значение дозорного, помещаются перед дозорным, а все элементы, превышающие значение дозорного, помещаются за дозорным (одинаковое число может идти с любой стороны). После выхода из раздела часовой находится в середине последовательности. Это называется операцией раздела;
- Рекурсивно сортируйте подмассивы элементов меньше контрольного значения и подмассивы элементов больше контрольного значения.
function quickSort2(ary, comparator = (a, b) => a - b) {
return partition(ary, comparator)
}
function partition(ary, comparator, start = 0, end = ary.length - 1, ) {
if (start >= end) {
return
}
var pivotIndex = Math.floor(Math.random() * (end - start + 1) + start)
var pivot = ary[pivotIndex]
swap(ary, pivotIndex, end)
for (var i = start - 1, j = start; j < end; j++) {
if (comparator(ary[j], pivot) < 0) {
i++
swap(ary, i, j)
}
}
swap(ary, i + 1, end)
partition(ary, comparator, start, i)
partition(ary, comparator, i + 2, end)
return ary
}