【译】算法的记录

Repeat, starting at the first element:
  If the element is the target element, stop
  Else, move to the next element

For i from 0 to n-1
  If i'th element is target_element
    Reture true
  Reture false

linearSearch = (arr, target) => {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === target) return true;
  }
  return false
}
复制代码

Repeat until the (sub)array is of size 0:
  Calculate the middle point of the current (sub)array
  If the target element is the middle element, stop
  Else if it's less than the middle:
    End point is now just to the left of the current middle, repeat
  Else if it's greater then the middle:
    Start point is now just to the right of the current middle, repeat

If no items
  Return false
If middle item is target_element
  Return  true
Else if target_element < middle item
  Update end point
  Search left half
Else if target_element > middle item
  Update start point
  Search right half

binarySearch = (arr, target, start, end) => {
  if(end >= start) {
    let mid = Math.floor((start+end)/2);
    if(arr[mid] === target) return mid;
    else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1);
    else return binarySearch(arr, target, mid+1, end);
  }
  return false;
}
复制代码

Set swap counter to a non-zero value
Repeat until the swap counter is equal to 0:
  Reset swap counter to 0
  Look at each adjacent pair:
    If two adjacent elements are not in order:
      Swap them
      Add one to the swap counter

Repeat until no swaps
  For i from 0 to n-2
    If i'th and i+1'th elements out of order
      Swap them

bubbleSort = arr => {
  for(let i = 0; i < arr.length-1; i++) {
    for(let j = 0; j < arr.length-i-1; j++) {
      if(arr[j] > arr[j+1]) {
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}
复制代码

Repeat until there is no unsorted elements remaining:
  Search unsorted part of data to find the smallest value
  Swap the found value with the first element of the unsorted part

For i from 0 to n-1
  Find smallest item between i'th item and last item
  Swap smallest item with i'th item

selectionSort = arr => {
  for(let i = 0; i < arr.length-1; i++) {
    let min = i;
    for(let j = i+1; j < arr.length; j++) {
      if(arr[j] < arr[min]) {
        min = j
      }
    }
    let temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
  return arr;
}
复制代码

Call the first element of the array sorted
Repeat until all elment are sorted:
  Insert next unsorted item into sorted part shifting the required number of items

For i from 1 to n-1
  Insert next unsorted item into sorted part shifting i items

insertionSort = arr => {
  for(let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i-1;
    while(j >= 0 && arr[j] > key) {
      arr[j+1] = arr[j];
      j = j-1;
    }
    arr[j+1] = key;
  }
  return arr;
}
复制代码

fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
…

fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
…

fact(n) = n * fact(n-1)

int fact(int n) {
  // base case
  if(n == 1)
    return 1;
  // recursive case
  else
    return n * fact(n-1)
}
复制代码

collatz = steps => {
  // base case
  if(step == 1) return 0;
  // recursive case: even numbers
  else if ((steps % 2) == 0) return 1+collatz(steps/2)
  // recursive case: odd numbers
  else return 1+collatz(3*steps+1)
}
复制代码

If only one element
  Return
Else
  Sort left half of elements
  Sort right half of elements
  Merge sorted halves

Sort the left half of the array (assuming n > 1)
Sort right half of the array (assuming n > 1)
Merge the two halves together

// to merge left subarray and right subarray
merge = (left, right) => {
  let resultArray = [], leftIndex = 0, rightIndex = 0;
    
  // concat values into the resultArray in order
  while(leftIndex < left.length && rightIndex < right.length) {
    if(left[leftIndex] < right[rightIndex]) {
      resultArray.push(left[leftIndex]);
      leftIndex++;
    } else {
      resultArray.push(right[rightIndex]);
      rightIndex++;
    }
  }
  // concat remaining element from either left OR right
  return resultArray
    .concat(left.slice(leftIndex))
    .concat(right.slice(rightIndex))
}

mergeSort = arr => {
  // if array has one element or is empty, no need to sort
  if(arr.length <= 1) return arr;
  
  const mid = Math.floor()
  // divide the array into left and right
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // merge back together using recursison
  return merge(mergeSort(left), mergeSort(right)))
}
复制代码