排序

[bWhirring]

冒泡排序

function bubbleSort<T>(array: T[]) {
  const { length } = array

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]]
      }
    }
  }
  return array
}

[bWhirring]

选择排序

function selectionSort<T>(array: T[]) {
  const { length } = array
  let min
  for (let i = 0; i < length; i++) {
    min = i
    for (let j = i; j < length; j++) {
      if (array[j] < array[min]) min = j
    }
    [array[i], array[min]] = [array[min], array[i]]
  }

  return array
}

[bWhirring]

插入排序

function insertionSort<T>(array: T[]) {
  const { length } = array
  let temp

  for (let i = 1; i < length; i++) {
    temp = array[i]
    let j = i
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = temp
  }
  return array
}

[bWhirring]

归并排序

function merge<T>(left: T[], right: T[]) {
  let i = 0;
  let j = 0;
  let result = []

  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++])
  }

  return result.concat(i < left.length ? left.slice(i) : right.slice(j))

}

function mergeSort<T>(array: T[]) {
  const { length } = array
  if (length > 1) {
    const middle = Math.floor(length / 2)
    const left = mergeSort(array.slice(0, middle))
    const right = mergeSort(array.slice(middle, length))
    console.log(left, right);
    array = merge(left, right)
  }

  return array
}

[bWhirring]

快速排序

function quickSort<T>(array: T[]) {
  if (array.length <= 1) return array

  const middle = Math.floor(array.length / 2)
  const pivot = array.splice(middle, 1)[0]

  const { length } = array

  const left = []
  const right = []

  for (let i = 0; i < length; i++) {
    array[i] > pivot ? right.push(array[i]) : left.push(array[i])
  }

  return quickSort(left).concat(pivot, quickSort(right))
}

[bWhirring]

计数排序

function countSort(array: number[]) {
  const { length } = array

  const newArray = []

  array.forEach(v => {
    if (!newArray[v]) {
      newArray[v] = 0
    }
    ++newArray[v]
  })

  let idx = 0

  newArray.forEach((val, i) => {
    while (val > 0) {
      array[idx++] = i;
      val--;
    }
  });

  return array
}