JS 实现一些简单的排序算法

冒泡排序

思路:循环数组,比较当前元素和下一个元素,小的那个向上冒泡,下一次循环继续上面的操作,排好序的数(在后面)不参与循环
时间复杂度:O(n2)

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

选择排序

思路:循环数组,选取一个最小的数字放到前面的有序序列中,下一次循环继续上面的操作,排好序的数(在前面)不参与循环
时间复杂度:O(n2)

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

插入排序

思路:将左侧序列看成一个有序序列,每次插入一个数字到该序列,插入时,从有序序列最右侧开始比较,较大的数后移
时间复杂度:O(n2)

function selectSort (array) {
  let len = array.length
  for (let i = 1; i < len; i++) {
    for (let j = i; j >= 0; j--) {
      if (array[j] < array[j-1]) {
        [ array[j], array[j-1] ] = [ array[j-1], array[j] ]
      } else break
    }
  }
}

快速排序

思路:选择一个基准元素 target(一般选择第一个数),将比 target 小的元素移动到数组左边,比 target 大的元素移动到数组右边,继续对 target 左侧和右侧的元素进行相同操作
时间复杂度:平均 O(nlogn),最坏 O(n2)

function quickSort (array, start = 0, end = array.length - 1) {
  if (start >= end) return
  let target = start
  let [ left, right ] = [ start, end ]
  while (left < right) {
    while (arr[right] >= arr[target] && left < right) {
      right--
    }
    while (arr[left] <= arr[target] && left < right) {
      left++
    }
    [ arr[left], arr[right] ] = [ arr[right], arr[left] ]
  }
  [ arr[target], arr[right] ] = [ arr[right], arr[target] ]
  quickSort(array, start, right - 1)
  quickSort(array, right + 1, end)
}
除特殊说明外本人博客均属原创,转载请注明出处:http://blog.johnhan.cn/blog_1108.html
京ICP备19044523号-1