Cyan's Blog

Appearance

常见算法手写 ​

冒泡 ​

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

选择 ​

js
function selectSort(arr) {
  const len = arr.length
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex],arr[i]]
  }
  return arr
}
function selectSort(arr) {
  const len = arr.length
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex],arr[i]]
  }
  return arr
}

插入 ​

js
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const temp = arr[i]
    let j = i
    while (j > 0) {
      if (arr[j - 1] > temp) {
        arr[j] = arr[j - 1]
      } else {
        break;
      }
      j -= 1
    }
    arr[j] = temp
  }
  return arr
}
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const temp = arr[i]
    let j = i
    while (j > 0) {
      if (arr[j - 1] > temp) {
        arr[j] = arr[j - 1]
      } else {
        break;
      }
      j -= 1
    }
    arr[j] = temp
  }
  return arr
}

归并 ​

js
function mergeSort(arr) {
  if (arr.length === 1) {return arr}
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid, arr.length)
  const orderLeft = mergeSort(left)
  const orderRight = mergeSort(right)
  const res = []
  while (orderLeft.length || orderRight.length) {
    if (orderLeft.length && orderRight.length) {
      res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
    } else if (orderLeft.length) {
      res.push(orderLeft.shift())
    } else if (orderRight.length) {
      res.push(orderRight.shift())
    }
  }
  return res
}
function mergeSort(arr) {
  if (arr.length === 1) {return arr}
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid, arr.length)
  const orderLeft = mergeSort(left)
  const orderRight = mergeSort(right)
  const res = []
  while (orderLeft.length || orderRight.length) {
    if (orderLeft.length && orderRight.length) {
      res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
    } else if (orderLeft.length) {
      res.push(orderLeft.shift())
    } else if (orderRight.length) {
      res.push(orderRight.shift())
    }
  }
  return res
}

快速 ​

js
function quickSort(arr) {
  if (arr.length < 2) return arr
  const left = []
  const right = []
  const mid = arr[0]
  for (let i = 1; i < arr.length; i+=1) {
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), mid, ...quickSort(right)]
}
function quickSort(arr) {
  if (arr.length < 2) return arr
  const left = []
  const right = []
  const mid = arr[0]
  for (let i = 1; i < arr.length; i+=1) {
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), mid, ...quickSort(right)]
}

二分搜索 ​

js
function binarySearch(arr,item) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const midElement = arr[mid];
    if (midElement > item) {
      high = midElement - 1
    } else if (midElement < item) {
      low = midElement + 1;
    } else {
      return mid
    }
  }
  return -1;
}
function binarySearch(arr,item) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const midElement = arr[mid];
    if (midElement > item) {
      high = midElement - 1
    } else if (midElement < item) {
      low = midElement + 1;
    } else {
      return mid
    }
  }
  return -1;
}