Письменные интервью часто включают различные алгоритмы. В этой статье кратко представлены некоторые обычно используемые алгоритмы и реализуют их в JavaScript.
1. Вставьте сортировку
1) Введение в алгоритм
Описание алгоритма вставки-это простой и интуитивно понятный алгоритм сортировки. Он работает, создавая упорядоченную последовательность, для несортированных данных, сканирования назад и вперед в отсортированной последовательности, найти соответствующую позицию и вставить ее. При реализации сортировки вставки обычно используется сортировка на месте (то есть дополнительное пространство O (1) требуется), поэтому во время процесса сканирования сзади на переднюю часть необходимо неоднократно перемещать задом наперед, чтобы обеспечить пространство вставки для последних элементов.
2) Описание и реализацию алгоритма
Вообще говоря, сортировка вставки реализуется на массиве с использованием на месте. Конкретный алгоритм описан следующим образом:
Начиная с первого элемента, элемент можно считать, что он отсортирован;
Выберите следующий элемент и сканируйте назад и вперед в уже отсортированной последовательности элементов;
Если элемент (отсортированный) больше, чем новый элемент, переместите элемент в следующую позицию;
Повторите шаг 3 до тех пор, пока не будет найден отсортированный элемент, где новый элемент меньше или равен;
После вставки нового элемента в эту позицию;
Повторите шаги от 2 до 5.
Реализация кода JavaScript:
функция insertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i - 1; while (j> = 0 && array [j]> key) {array [j + 1] = array [j]; J--; } массив [j + 1] = key; } return Array; } else {return 'массив - это не массив!'; }}3) Анализ алгоритма
Лучший случай: входные массивы отсортированы в порядке возрастания. T (n) = O (n)
В худшем случае: массив ввода сортируется в порядке убывания. T (n) = O (n2)
Среднее: t (n) = O (n2)
Два, бинарная вставка
1) Введение в алгоритм
Бинарная сортировка с внутренними и сортировкой-это алгоритм сортировки, который вносит незначительные изменения в алгоритме прямой вставки. Самая большая разница между ним и алгоритмом сортировки прямой вставки заключается в том, что при поиске позиций вставки используется метод бинарного поиска, который имеет определенное улучшение скорости.
2) Описание и реализацию алгоритма
Вообще говоря, сортировка вставки реализуется на массиве с использованием на месте. Конкретный алгоритм описан следующим образом:
Начиная с первого элемента, элемент можно считать, что он отсортирован;
Выберите следующий элемент и найдите позицию первого числа больше, чем он в уже отсортированной последовательности элементов;
После вставки нового элемента в эту позицию;
Повторите два вышеуказанных шага.
Реализация кода JavaScript:
function BinaryAnsertionSt (Array) {if (object.prototype.tostring.call (массив) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i], слева = 0, правый = i -1; while (слева <= справа) {var middle = parseint ((слева + справа) / 2); if (key <array [midne]) {right = middle - 1; } else {Left = Middle + 1; }} for (var j = i-1; j> = слева; j--) {array [j + 1] = array [j]; } массив [слева] = key; } return Array; } else {return 'массив - это не массив!'; }}3) Анализ алгоритма
Лучший случай: t (n) = o (nlogn)
Худший случай: t (n) = O (n2)
Среднее: t (n) = O (n2)
3. Выберите сортировку
1) Введение в алгоритм
Selection-Sort-это простой и интуитивно понятный алгоритм сортировки. Как это работает: сначала найдите наименьший (большой) элемент в несортированной последовательности, сохраните его в исходном положении отсортированной последовательности, затем продолжайте искать наименьший (большой) элемент из оставшихся несортированных элементов, а затем поместите его в конце отсортированной последовательности. И так далее, пока все элементы не будут отсортированы.
2) Описание и реализацию алгоритма
Прямой выбор N-записей можно получить с помощью N-1 проходов для непосредственного выбора и сортировки. Конкретный алгоритм описан следующим образом:
Первоначальное состояние: неупорядоченная область - r [1..n], а упорядоченная область пуста;
Когда начинается упорядочение i-th (i = 1,2,3 ... n-1), текущие и неупорядоченные области являются r [1..i-1] и r (i..n) соответственно. Этот заказ выбирает запись r [k] с наименьшим ключевым словом из нынешней неупорядоченной области и обменивает ее с первой записью R неупорядоченной области, так что R [1..i] и R [i+1..n) становятся новой упорядоченной областью с одним увеличением количества записей и новой неупорядоченной областью с одним уменьшением числа записей;
Поездка N-1 заканчивается, и массив заказан.
Реализация кода JavaScript:
function selectionord (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; for (var i = 0; i <len - 1; i ++) {var min = array [i]; for (var j = i+1; j <len; j ++) {if (array [j] <min) {temp = min; min = массив [j]; Array [j] = temp; }} массив [i] = min; } return Array; } else {return 'массив - это не массив!'; }}3) Анализ алгоритма
Лучший случай: t (n) = O (n2)
Худший случай: t (n) = O (n2)
Среднее: t (n) = O (n2)
4. Сортировка пузырьков
1) Введение в алгоритм
Сортировка пузырьков - это простой алгоритм сортировки. Он неоднократно посещает последовательности, которые будут сортироваться, сравнивают два элемента за раз и меняют их, если они неверны. Работа по посещению последовательности повторяется до тех пор, пока обмен не требуется, то есть последовательность не была отсортирована. Происхождение этого алгоритма заключается в том, что тем меньше элемент будет медленно «плавать» до вершины последовательности через обмен.
2) Описание и реализацию алгоритма
Конкретный алгоритм описан следующим образом:
Сравните соседние элементы. Если первый больше, чем у второго, обменяйте два из них;
Делайте ту же работу для каждой пары соседних элементов, от начала первой пары до конца последней пары, чтобы последний элемент должен был быть самым большим числом;
Повторите вышеуказанные шаги для всех элементов, кроме последнего;
Повторите шаги с 1 по 3, пока сортировка не будет завершена.
Реализация кода JavaScript:
функция Bubblesort (Array) {if (object.prototype.tostring.call (массив) .slice (8, -1) === 'array') {var len = array.length, temp; for (var i = 0; i <len - 1; i ++) {for (var j = len - 1; j> = i; j--) {if (array [j] <array [j - 1]) {temp = array [j]; Array [j] = массив [j - 1]; массив [j - 1] = temp; }}} return Array; } else {return 'массив - это не массив!'; }}3) Анализ алгоритма
Лучший случай: t (n) = O (n)
Худший случай: t (n) = O (n2)
Среднее: t (n) = O (n2)
5. Быстрый сортировка
1) Введение в алгоритм
Основная идея быстрой сортировки: разделите записи, которые будут сортироваться на две независимые части через один заказ, и ключевые слова некоторых записей меньше, чем у другой части. Затем две записи могут продолжать сортировать их отдельно, чтобы достичь порядка всей последовательности.
2) Описание и реализацию алгоритма
Быстрая сортировка использует метод деления, чтобы разделить строку на два подраздел. Конкретный алгоритм описан следующим образом:
Выбор элемента из последовательности называется «Принцип» (Pivot);
Пересмотреть порядок последовательность, все элементы с меньшим, чем эталонное значение, расположены перед ссылкой, и все элементы с большим, чем эталонное значение, расположены за эталоном (одно и то же число может быть размещено с обеих сторон). После выхода этого раздела ссылка находится в середине последовательности. Это называется операцией раздела;
Рекурсивно сортируют подпоследовательности, меньшие, чем эталонный элемент, и подпоследовательности больше, чем эталонный элемент.
Реализация кода JavaScript:
// Метод одна функция QuickSort (массив, слева, справа) {if (object.prototype.tostring.call (массив) .slice (8, -1) === 'array' && typeof left === 'number' && typef ruight === '№ 1) {if (right right) {var x = rugh [справа], i = temp - 1, temp') {if (справа) {var x = array for (var j = слева; j <= справа; j ++) {if (array [j] <= x) {i ++; temp = array [i]; Array [i] = Array [j]; Array [j] = temp; }} QuickSort (массив, слева, i - 1); QuickSort (массив, i + 1, справа); }; } else {return 'массив - это не массив, или влево или справа - это не число!'; }} var aaa = [3, 5, 2, 9, 1]; QuickSort (AAA, 0, AAA.Length - 1); console.log (aaa); // Метод 2 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]); }} вернуть QuickSort (слева) .concat ([pivot], QuickSort (справа)); };3) Анализ алгоритма
Лучший случай: t (n) = o (nlogn)
Худший случай: t (n) = O (n2)
Среднее: t (n) = O (nlogn)
6. Сортировка кучи
1) Введение в алгоритм
Сортировка кучи относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Упаковка - это структура, которая является приблизительно полностью двоичным деревом и удовлетворяет свойствам укладки: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла.
2) Описание и реализацию алгоритма
Конкретный алгоритм описан следующим образом:
Начальная последовательность ключевых слов, которые должны быть сортированы (R1, R2 ... RN), построена в большую верхнюю кучу, которая является начальной неупорядоченной областью;
Обмен верхний элемент Heap R [1] с последним элементом r [n], и в настоящее время получается новая неупорядоченная область (R1, R2, ... rn-1) и новая упорядоченная область (RN), и R [1,2 ... n-1] <= r [n] удовлетворяется;
Поскольку новая топ-куча R [1] после обмена может нарушить свойства кучи, необходимо регулировать текущую неупорядоченную область (R1, R2, ... RN-1) на новую кучу, а затем снова обмениваться R [1] с последним элементом непорядочной области, чтобы получить новую неупорядоченную область (R1, R2 ... RN-2) и новая заказанная область (RN-1, RN). Повторите этот процесс, пока количество элементов в упорядоченной области не станет N-1, а весь процесс сортировки не будет завершен.
Реализация кода JavaScript:
/*Метод Описание: Heap Sort @param массив массив для сортировки*/function heapsort (массив) {if (object.prototype.tostring.call (массив) .slice (8, -1) === 'Array') {// Сборка heap heap heapize = ray.length, temp; for (var i = math.floor (Heapizize / 2); i> = 0; i--) {Heapify (массив, i, Heapizize); } // Heap Sort for (var j = Heapize-1; j> = 1; j--) {temp = массив [0]; массив [0] = массив [j]; Array [j] = temp; Heapify (массив, 0, -Heapsize); }} else {return 'массив не массив!'; }}/ * Метод Описание: Сохраняйте свойства Heap @param arr Arry @param x массив Supcript @param len heap размер */функция Heapify (arr, x, len) {if (object.prototype.tostring.call (arr) .slice (8, -1) === 'ray' && typef x == 'number') 1, больше всего = x, темп; if (l <len && arr [l]> arr [самый большой]) {самый большой = l; } if (r <len && arr [r]> arr [самый большой]) {самый большой = r; } if (самый большой! = x) {temp = arr [x]; arr [x] = arr [самый большой]; arr [самый большой] = темп; HeApify (arr, lagry, len); }} else {return 'arr не массив, или x не является числом!'; }}3) Анализ алгоритма
Лучший случай: t (n) = o (nlogn)
Худший случай: t (n) = o (nlogn)
Среднее: t (n) = O (nlogn)
7. Заказ
1) Введение в алгоритм
Сортировка слияния - это эффективный алгоритм сортировки, основанный на операции слияния. Этот алгоритм является очень типичным применением разделения и завоевания. Сортировка слияния - это стабильный метод сортировки. Объединить упорядоченные последующие последствия, чтобы получить полностью упорядоченную последовательность; то есть сделайте каждую последующую последовательность в первом порядке, а затем сделайте заказ сегментов последующих сегментов. Если две заказанные таблицы объединены в одну упорядоченную таблицу, это называется 2-й пустого слияния.
2) Описание и реализацию алгоритма
Конкретный алгоритм описан следующим образом:
Разделите входную последовательность длины N на две последующие последствия длины N/2;
Эти две последствия отсортированы вместе отдельно;
Объедините два отсортированных последующих, в окончательную отсортированную последовательность.
Реализация кода JavaScript:
Функция Mergesort (Array, P, R) {if (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, P, Q); Mergesort (массив, q + 1, r); слияние (Array, P, Q, R); }} функция Merge (Array, P, Q, r) {var n1 = q - p + 1, n2 = r - q, левая = [], правая = [], m = n = 0; for (var i = 0; i <n1; i ++) {Left [i] = массив [p+i]; } for (var j = 0; j <n2; j ++) {right [j] = массив [q + 1 + j]; } left [n1] = right [n2] = number.max_value; for (var k = p; k <= r; k ++) {if (left [m] <= right [n]) {array [k] = слева [m]; M ++; } else {array [k] = right [n]; n ++; }}}3) Анализ алгоритма
Лучший случай: t (n) = O (n)
Худший случай: t (n) = o (nlogn)
Среднее: t (n) = O (nlogn)
8. Сортировка ведра
1) Введение в алгоритм
Принцип сортировки ведра: при условии, что входные данные равномерно распределены, данные делятся на ограниченное количество ведер, и каждое ведро сортируется отдельно (можно использовать другие алгоритмы сортировки или продолжать использовать сортировку ведра рекурсивным образом).
2) Описание и реализацию алгоритма
Конкретный алгоритм описан следующим образом:
Установите количественный массив в качестве пустого ведра;
Итерация через входные данные и поместите данные в соответствующее ведро один за другим;
Сортировать каждое ведро, которое не пустое;
Сплайсировать отсортированные данные из пустого ведра.
Реализация кода JavaScript:
/*Метод Описание: Сорт -сортировка @param массив массив @param Число ведра*/ Функция Bucketsort (Array, Num) {if (array.length <= 1) {return Array; } var len = array.length, buckets = [], result = [], min = max = массив [0], regex = '/^[1-9]+[0-9]*$/', пространство, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); для (var i = 1; i <len; i ++) {min = min <= массив [i]? Мин: массив [i]; max = max> = массив [i]? Макс: массив [i]; } space = (max - min + 1) / num; for (var j = 0; j <len; j ++) {var index = math.floor ((массив [j] - min) / space); if (buckets [index]) {// Непустые ведра, вставьте сортировку var k = buckets [index] .length - 1; while (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = buckets [index] [k]; k--; } ведра [index] [k + 1] = array [j]; } else {// пустое ведро, инициализируйте ведра [index] = []; ведра [index] .push (массив [j]); }} while (n <num) {result = result.concat (buckets [n]); n ++; } return Result; }3) Анализ алгоритма
В лучшем случае сортировки ведра, линейное время o (n), сложность времени сортировки ведра зависит от сложности времени сортировки данных между ведрами, потому что временная сложность других частей составляет O (n). Очевидно, что чем меньше ведро разделяется, тем меньше данных, тем меньше времени требуется для его сортировки. Но соответствующее потребление пространства увеличится.
9. Подсчет сортировки
1) Введение в алгоритм
Подсчет сортирования - это стабильный алгоритм сортировки. Count Sorting использует дополнительный массив C, где I-Th-элемент-это количество элементов со значением, равным I, в массиве A для сортировки. Затем, согласно массиву C, элементы в A расположены в правильном положении. Это может только сортировать целые числа.
2) Описание и реализацию алгоритма
Конкретный алгоритм описан следующим образом:
Найдите самые большие и самые маленькие элементы в массиве, которые будут отсортированы;
Подсчитайте количество раз каждый элемент со значением I в массиве, и храните его в i-й пункте массива C;
Накапливать все подсчеты (начиная с первого элемента в C, каждый элемент и предыдущий элемент добавляются);
Обратный массив целевого заполнения: поместите каждый элемент I в элемент C (i) нового массива и вычтите C (i) на 1 для каждого элемента.
Реализация кода JavaScript:
FUNCTION COUNTITYSORT (Array) {var len = array.length, b = [], c = [], min = max = array [0]; для (var i = 0; i <len; i ++) {min = min <= массив [i]? Мин: массив [i]; max = max> = массив [i]? Макс: массив [i]; C [Array [i]] = c [Array [i]]? C [массив [i]] + 1: 1; } for (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } for (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = массив [k]; C [массив [k]]-; } return b; }3) Анализ алгоритма
Когда входной элемент составляет n целых числа между 0 и K, его время выполнения составляет O (N + K). Сортировка подсчета не является сортировкой сравнения, а скорость сортировки быстрее, чем любой алгоритм сортировки сравнения. Поскольку длина массива C, используемого для подсчета, зависит от диапазона данных в массиве, который будет сортироваться (равна разнице между максимальными и минимальными значениями массива, который будет сортирован плюс 1), для сортировки подсчета требуется много времени и памяти для массивов с большим диапазоном данных.