Алгоритмы, эта тема немного большая.
На самом деле алгоритм - это очень широкое понятие. Все программы, которые мы пишем, можно назвать алгоритмами, потому что алгоритм - это логика для обработки проблем, классификации проблем, абстрагирования единой парадигмы, а затем присвоения этой парадигмы имени. Например: quick Сортировать.
Итак, здесь мы рассмотрим, какие алгоритмы обычно используются во внешнем интерфейсе.
рекурсия
рекурсивный алгоритм: английский: алгоритм рекурсии) в информатике относится к методу решения проблемы путем многократного разбиения ее на подзадачи одного типа. Большинство языков программирования поддерживают функциивызывающий сам себя, в этих языках функции могут рекурсивно вызывать сами себя.
Два элемента рекурсии:
- называть себя
- Может выскочить из петли
факториал
n! = n*(n-1)...21
6! = 6 * 5 * 4 * 3 * 2 *1
Правило: Факториал n есть произведение убывающих значений от n
function factorial(number){
if(number==1) {
return number;
} else{
return number*factorial(number-1);
}
}Последовательность Фибоначчи
Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Найдите n-е число
первое число: 1
Второй номер: 1
Третий номер: 1+1
Третье число: 2+1+1
Четвертое число: 3+2+1+1
Пятое число: 4+3+2+1+1
...
Правило: Последний член равен сумме первых двух
function fibonacci(number) {
if (number <= 2) {
return 1;
}
return fibonacci(number-1) + fibonacci(number - 2)
}Алгоритм сортировки
алгоритм пузырьковой сортировки: он многократно проходит через последовательность для сортировки, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Работа по посещению последовательности повторяется до тех пор, пока перестановки не понадобятся, то есть последовательность отсортирована.
Сравните процесс
- Сравните соседние элементы. Если первый больше второго, поменяйте их местами.
- Сделайте то же самое для каждой пары соседних элементов, от первой пары в начале до последней пары в конце. На этом этапе последний элемент должен быть наибольшим числом.
- Повторите вышеуказанные шаги для всех элементов, кроме последнего.
- Продолжайте повторять описанные выше шаги для все меньшего и меньшего количества элементов каждый раз, пока не останется пар чисел для сравнения.
По возрастанию 6 2 7 9 5
Первое пузырение: 2 6 7 9 5
Второе пузырение: 2 5 7 9 6
...
// 升序比较
function bubbleSort(arr) {
var nArr = arr.slice();
var temp;
if (nArr.length > 0) {
for (var i = 0; i < nArr.length; i++){
for (var l = i; l < (nArr.length - 1); l++){
if (nArr[i] > nArr[l+1]) {
temp = nArr[i];
nArr[i] = nArr[l+1];
nArr[l+1] = temp;
}
}
}
}
return nArr;
}Алгоритм быстрой сортировки: Quicksort — один из самых быстрых алгоритмов сортировки для обработки больших наборов данных. Это алгоритм «разделяй и властвуй»рекурсияспособ сортировки данных по порядкуРазложить на отдельные подпоследовательности, содержащие меньшие и большие элементы. Алгоритм продолжает повторять этот шаг, пока все данные не будут в порядке.
Инструкции по сортировке
- Шаг 1: Выбор базового значения. Эталонное значение может быть выбрано произвольно
- Шаг 2: Работа с разделами. Сравните каждый элемент с эталоном по порядку, думая о двух подмножествах (больше, чем эталон, меньше, чем эталон).
- Третий шаг — рекурсивная операция. Повторяйте шаги 1 и 2 для обоих подмножеств, пока во всех подмножествах не останется только один элемент.
function qSort(arr) {
if (arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) { // 注意这里的起始值，因为有一个作为flag了
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return qSort(left).concat(pivot, qSort(right));
}алгоритм поиска
алгоритм бинарного поиска: Также известный как бинарный поиск, это более эффективный метод поиска. Однако половинный поиск требует, чтобы линейная таблица имела последовательную структуру хранения, а элементы в таблице располагались по порядку по ключу.
Найти инструкции
1. Установить первую позицию массива на нижнюю границу (0)
2. Установить позицию последнего элемента массива на верхнюю границу (длина массива минус 1).
3. Если нижняя граница меньше или равна верхней границе, выполните следующие действия.
- Установите среднюю точку как (верхняя граница плюс нижняя граница), деленная на 2
- Если элемент в средней точке меньше значения запроса, установите нижнюю границу на нижний индекс элемента средней точки плюс 1.
- Если элемент в средней точке больше, чем значение запроса, установите верхнюю границу на нижний индекс элемента средней точки минус 1.
- В противном случае элемент средней точки является данными для поиска и может быть возвращен.
Обратите внимание, что массив здесь должен бытьаккуратныйиз
function binSearch(arr, data) {
var upperBound = arr.length - 1;
var lowerBound = 0;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
if (arr[mid] < data) {
lowerBound = mid + 1;
}
else if(arr[mid] > data) {
upperBound = mid - 1;
} else {
return mid;
}
}
return -1;
}алгоритм бинарного дерева
бинарное дерево
Двоичное дерево — это древовидная структура с не более чем двумя поддеревьями на узел. Обычно поддеревья называют «левым поддеревом» и «правым поддеревом». Двоичные деревья часто используются для реализации двоичных деревьев поиска и двоичных куч.
Свойства бинарных деревьев
- Каждый узел имеет не более двух поддеревьев, а максимальная степень узла равна 2.
- Левое поддерево и правое поддерево идут по порядку, и порядок нельзя изменить
- Даже если узел имеет только одно поддерево, необходимо различать левое и правое поддеревья.
используется здесьрекурсия-обход предварительного заказадревовидная структура
var preOrder = function (node) {
if (node) {
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}