轻键快码

Javascript 实现算法

轻键快码 Javascript算法

冒泡排序

利用循环,每次将较大的数与较小的数进行交换。

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

选择排序

每次循环找到最小的数将其放到第一位,然后从下一个位置开始。

function selectSort (arr) {
 let res = arr.slice(0)
 let min
 for (let i = 0; i < res.length - 1; i++) {
  min = i
  for (let j = i + 1; j < res.length - 1; j++) {
     if (res[j] < res[min]) {
        min = j
     }
     [res[min], res[i]] = [res[i], res[min]]
  }
 }
 return res
}

插入排序

如果外循环的数比内循环小,数组元素向右移,将较小的数放在前面

function insertSort (arr) {
  let res = arr.slice(0)
  let temp, inner
  for (let outer = 1 ; outer < res.length; outer++) {
    temp = res[outer]
    inner = outer
    while (inner > 0 && res[inner - 1] >= temp) {
     res[inner] = res[inner - 1]
     inner--
    }
    res[inner] = temp
  }
  return res
}

希尔排序

定义一个间隔序列,每次比较间隔两边的数,然后将较大的数与较小的数交换。

const gaps = [701, 301, 132, 57, 23, 10, 4, 1]

function shellSort (arr) {
  let res = arr.slice(0)
  let gap, current
  for (let k = 0; k < gaps.length; k++) {
    gap = gaps[k]
    for (let i = gap; i < res.length; i += gap) {
      current = res[i]
      for (var j = i; j >= gap && res[j - gap] > current; j -= gap) {
        res[j] = res[j - gap]
      }
      res[j] = current
    }
  }
  return res
}

归并排序

首先将数据分解成只有一个元素的数组,再创建左右两个数组将拍好序的数据合并起来。

function mergeSort(arr, start, end) {
  start = start || 0
  end = end || arr.length
  if (Math.abs(end - start) <= 1) {
    return []
  }
  let middle = Math.ceil((start + end) / 2)
  mergeSort(arr, start, middle)
  mergeSort(arr, middle, end)
  return mergeArr(arr, start, middle, end)
}

function mergeArr (arr, start, middle, end) {
  let left = []
  let right = []
  let leftSize = middle - start
  let rightSize = end - middle
  let maxSize = Math.max(leftSize, rightSize)
  let size = end - start
  for (let i = 0; i < maxSize; i++) {
    if (i < leftSize) {
      left.push(arr[start + i])
    }
    if (i < rightSize) {
      right.push(arr[middle + i])
    }
  }
  for (let j = 0; j < size; j++) {
    if (left[0] && right[0]) {
      if (left[0] > right[0]) {
        arr[start + j] = right.shift()
      } else {
        arr[start + j] = left.shift()
      }
    } else if (left[0]) {
      arr[start + j] = left.shift()
    } else {
      arr[start + j] = right.shift()
    }
  }
  return arr
}

快速排序

首先找到一个基准值,通过递归的方式不断把数据分解为包含较大和较小元素的子数组,在将其合并。

function quickSort (arr) {
 if (!arr.length) return []
 let left = []
 let right = []
 let radix = arr[0]
 for (let i = 1; i < arr.length; i++) {
   if (arr[i] < radix) {
     left.push(arr[i])
   } else {
    right.push(arr[i])
   }
 }
 return quickSort(left).concat(radix, quickSort(right))
}