各种排序算法学习笔记

2021/9/11 14:34:51

本文主要是介绍各种排序算法学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序——确定一个分割点,左右站队,递归进行 时间复杂度为 O(n(logn))

function quickSort(array) {
  if (array.length < 2) return array
  let pivot = array[0],
    left = [],
    right = [];
  for (let i = 1; i < array.length; i++) {
    let value = array[i]
    if (value < pivot) {
      left.push(value)
    } else {
      right.push(value)
    }
  }
  return quickSort(left).concat(pivot, quickSort(right))
}
console.log('quickSort', quickSort([9, 2, 3, 1, 4, 5, 4, 3]))

插入排序:

function insertSort(array) {
  // 第一个元素是排好序的,从第二个元素开始,往已排序中插入
  for (let i = 1; i < array.length; i++) {
    let wait = array[i]
    let j
    for (j = i - 1; j >= 0; j--) {
      if (array[j] > wait) {
        array[j + 1] = array[j]
      } else {
        break
      }
    }
    array[j + 1] = wait
  }
  return array
}

console.log('insertSort', insertSort([9, 2, 3, 1, 4, 5, 4, 3]))

希尔(shell)排序 插入排序的改进版, 又叫做缩小增量排序

function shellSort(arr) {
  let len = arr.length;
  // gap 即为增量
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let j = i;
      let current = arr[i];
      while (j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
  return arr
}
console.log('shellSort', shellSort([9, 2, 3, 1, 4, 5, 4, 3]))

function myShellSort(arr) {
  for (let step = Math.floor(arr.length / 2); step > 0; step = Math.floor(step / 2)) {
    for (let i = step; i < arr.length; i++) {
      let j = i - step;
      let target = arr[i]
      while (j >= 0 && arr[j] > target) {
        arr[j + step] = arr[j]
        j = j - step
      }
      arr[j + step] = target
    }
  }
  return arr
}

console.log('myShellSort', myShellSort([9, 2, 3, 1, 4, 5, 4, 3]))



这篇关于各种排序算法学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程