使用JavaScript實(shí)現(xiàn)部分算法

sshe 發(fā)布于2019-08-20 13:51 / 1389人閱讀

摘要：二分查找二分查找是一種在有序列表中查找某一特定元素的搜索算法。如果出現(xiàn)列表為空，則表示找不到該元素。這種搜索算法每一次比較都使搜索范圍縮小一半，時(shí)間復(fù)雜度為。

二分查找

二分查找是一種在有序列表中查找某一特定元素的搜索算法。從列表的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在列表大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果出現(xiàn)列表為空，則表示找不到該元素。這種搜索算法每一次比較都使搜索范圍縮小一半，時(shí)間復(fù)雜度為Ο(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));
}

選擇排序

選擇排序和冒泡排序很相近，不多次反復(fù)交換，是找到最大或最小的元素的位置，再做交換

"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;
}