使用JavaScript实现部分算法

摘要：二分查找二分查找是一种在有序列表中查找某一特定元素的搜索算法。如果出现列表为空，则表示找不到该元素。这种搜索算法每一次比较都使搜索范围缩小一半，时间复杂度为。

二分查找是一种在有序列表中查找某一特定元素的搜索算法。从列表的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在列表大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果出现列表为空，则表示找不到该元素。这种搜索算法每一次比较都使搜索范围缩小一半，时间复杂度为Ο(logn) 。

"use strict"
function binarySearch(orderedArr, start, end, value) {
  if (start > end) {
    return -1;
  }
  const middle = Math.floor((start + end) / 2);
  const middleVal = orderedArr[middle];
  let newStart = start;
  let newEnd = end;
  if (middleVal > value) {
    newEnd = middle - 1;
  } else if ( middleVal < value) {
    newStart = middle + 1;
  } else {
    return middle;
  }
  return binarySearch(orderedArr, newStart, newEnd, value);
}

function find(arr, value){
  return binarySearch(arr, 0, arr.length - 1, value);
}

"use strict"
/**
 * (1)
 */
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const leftArr = [];
  const rightArr = [];
  for(let i = 0, len = arr.length; i < len; i++) {
    const item = arr[i];
    if (item > pivot) {
      rightArr.push(item);
    } else {
      leftArr.push(item);
    }
  }
  return quickSort(leftArr).concat([pivot], quickSort(rightArr));
}

"use strict"
/**
 * (2)
 */
function quickSort(arr, start, end) {
  if (start > end) return;
  const pivot = arr[end];
  let position = start;
  for (let i = start; i < end; i++) {
    if (arr[i] < pivot ) {
      [arr[position], arr[i]] = [arr[i], arr[position]]; // swap
      position++;
    }
  }
  [arr[position], arr[end]] = [arr[end], arr[position]];
  quickSort(arr, start, position - 1);
  quickSort(arr, position + 1, end);
}
function sort(arr) { 
  return quickSort(arr, 0, arr.length - 1);
}

"use strict"
function bubbleSort(arr) {
  if (arr.length <=1 ) return arr;
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = i+1; j < len; j++) {
      if (arr[i] < arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  return arr;
}

先拆分再合并

"use strict"
/**
 * 递归方式（可能栈溢出）
 */

function merge(leftArr, rightArr) { // 合并
   const newArr = [];
   while (leftArr.length > 0 && rightArr.length > 0) {
       if (leftArr[0] < rightArr[0]) {
           newArr.push(leftArr.shift());
       } else {
           newArr.push(rightArr.shift());
       }
   }
   return newArr.concat(leftArr).concat(rightArr);
}

function mergeSort(arr) { // 拆分
   if (arr.length <= 1) return arr;
   const middle = Math.floor(arr.length / 2);
   const leftArr = arr.slice(0, middle);
   const rightArr = arr.slice(middle);
   return merge(mergeSort(leftArr), mergeSort(rightArr));
}

选择排序和冒泡排序很相近，不多次反复交换，是找到最大或最小的元素的位置，再做交换

"use strict"
function selectSort(arr) {
  if (arr.length <= 1) return arr;
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let tempIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[tempIndex]) {
        tempIndex = j;
      }
    }
    [arr[i], arr[tempIndex]]=[arr[tempIndex], arr[i]];
  }
  return arr;
}

"use strict"
function insertSort(arr) {
  if (arr.length <= 1) return arr;
  const len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; 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;
}