Библиотека коллекций интерфейсных алгоритмов

внешний интерфейс алгоритм JavaScript модульный тест

1. Введение

Библиотека сбора кодов интерфейсных алгоритмов

Он направлен на то, чтобы помочь вам улучшить свой уровень кодирования javascript, спецификацию кода и спокойно справиться с самыми сложными вопросами алгоритмов, которые задают интервьюеры.

Это коллекция библиотек общих вопросов для собеседования по алгоритму js, включая тесты, добро пожаловатьstar, если в библиотеке нет алгоритма, пожалуйста, отправьте задачу или PR для его завершения.

Когда дело доходит до алгоритмов, давайте поговорим здесь о временной сложности. Временная сложность: временная сложность алгоритма — это функция, описывающая время работы алгоритма. Чем ниже временная сложность, тем выше эффективность.

2. О спецификации кода

Как говорится, никакие правила не могут создать круг, поэтому вы должны развивать хорошие привычки кодирования в обычное время.

3. О тестировании кода

Обучение тестированию и непрерывной интеграции (сокращенно CI) означает, что в проекте любые изменения, внесенные кем-либо в кодовую базу, заставят сервер CI автоматически построить проект, автоматически запустить тесты и даже автоматически развернуться в тестовой среде. Преимущество этого в том, что вы можете найти проблемы в любое время и устранить их в любое время.Поскольку стоимость устранения проблем со временем растет, чем раньше вы их обнаружите, тем ниже затраты на ремонт).

4. Общие алгоритмы

4.1 Бинарный поиск

Введение алгоритма

Двоичный поиск, также известный как половинный поиск, представляет собой алгоритм поиска, который находит определенный элемент в упорядоченном массиве. Процесс поиска можно разбить на следующие этапы: (1) Сначала начинаем поиск со среднего элемента упорядоченного массива, если это именно целевой элемент (т.е. тот элемент, который нужно найти), процесс поиска завершается, иначе переходим к следующему шагу. (2) Если целевой элемент больше или меньше среднего элемента, выполните поиск в половине области массива, которая больше или меньше среднего элемента, а затем повторите операцию первого шага. (3) Если массив определенного шага пуст, это означает, что целевой элемент не может быть найден.

Код ссылки:

нерекурсивный алгоритм

function binary_search(arr,key){
  var low=0,
  high=arr.length-1;
  while(low<=high){
     var mid=parseInt((high+low)/2);
     if(key==arr[mid]){
        return mid;
     }else if(key>arr[mid]){
        low=mid+1;
     }else if(key<arr[mid]){
        high=mid-1;
    }else{
      return -1;
    }
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,10);
alert(result); // 9 返回目标元素的索引值

рекурсивный алгоритм

function binary_search(arr,low,high,key){
  if(low>high){
    return -1;   
  }
  var mid=parseInt((high+low)/2);
  if(arr[mid]==key){
    return mid;
  }else if(arr[mid]>key){
    high=mid-1;
    return binary_search(arr,low,high,key);
  }else if(arr[mid]<key){
    low=mid+1;
    return binary_search(arr,low,high,key);
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,0,13,10);
alert(result); // 9 返回目标元素的索引值

4.2 Сортировка

4.2.1 Пузырьковая сортировка

Введение алгоритма

Разобрать:

  1. Сравните два соседних элемента и поменяйте местами, если первый больше второго.
  2. В первом раунде последний элемент должен быть самым большим.
  3. Чтобы сравнить два соседних элемента, следуйте методу шага 1. В это время, поскольку последний элемент уже является самым большим, последний элемент не нужно сравнивать.

реализация js-кода

function bubble_sort(arr){
  for(var i=0;i<arr.length-1;i++){
    for(var j=0;j<arr.length-i-1;j++){
      if(arr[j]>arr[j+1]){
        var swap=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=swap;
      }
    }
  }
}

var arr=[3,1,5,7,2,4,9,6,10,8];
bubble_sort(arr);
console.log(arr);
4.2.2 Быстрая сортировка

реализация js-кодаАнализ: Быстрая сортировка — это улучшение пузырьковой сортировки.При первом проходе данные делятся на две части, причем одна часть меньше, чем все данные в другой части. Затем он вызывается рекурсивно, выполняя быструю сортировку с обеих сторон.

function quick_sort(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 quick_sort(left).concat([pivot],quick_sort(right));
}

var arr=[5,6,2,1,3,8,7,1,2,3,4,7];
console.log(quick_sort(arr));
4.2.3 Сортировка вставками

Введение алгоритма

Разобрать:

  1. Начиная с первого элемента, элемент можно считать отсортированным
  2. Возьмите следующий элемент и просканируйте его от начала до конца в отсортированной последовательности элементов.
  3. Если элемент (отсортированный) больше нового элемента, переместите элемент в следующую позицию
  4. Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
  5. Вставьте новый элемент в следующую позицию
  6. повторить шаг 2

реализация js-кода

function insert_sort(arr){
  var i=1,
  j,key,len=arr.length;
  for(;i<len;i++){
    var j=i;
    var key=arr[j];
    while(--j>-1){
      if(arr[j]>key){
        arr[j+1]=arr[j];
      }else{
        break;
      }
    }

    arr[j+1]=key;
  }

  return arr;
}

insert_sort([2,34,54,2,5,1,7]);

5. Наконец

Эта библиотека, являющаяся лишь небольшой частью коллекции, может оставить сообщение или поднять вопрос или PR дополнить общий алгоритм, чтобы больше людей узнали.

Категории