JS排序算法实现

本文介绍一下快速排序、归并排序、冒泡排序的JS实现。

一、快速排序

思想:分治法

  1. 选定基数,将数组按照大小归到基数左右两边;
  2. 对第一步基数两边的子数组,递归执行第一步
function quickSort(list, left = 0, right = list.length - 1) {
  if (left >= right) return
  let lIdx = left, rIdx = right, mid = list[right]
  list.slice(left, right + 1).forEach(item => item > mid ? list[rIdx--] = item : list[lIdx++] = item)
  quickSort(list, left, rIdx - 1)
  quickSort(list, rIdx + 1, right)
}

二、归并排序

思想:(分治法)将两个有序数组合并成一个大的有序数组,只需要不断地将两个列表中的排头元素中较小(升序,降序则是较大)的一个取出放到新数组,不断重复此过程直到两个原数组中的数都被取完。对于每一个数组,首先划分为长度为1的数组(天然有序),然后两两合并为有序数组,不断重复,最终整个数组都将有序。

function merge(l1, l2) {
  let i1 = 0, i2 = 0, result = []
  while (i1 < l1.length && i2 < l2.length) result.push(l1[i1] < l2[i2] ? l1[i1++] : l2[i2++])
  let rest = i1 >= l1.length ? l2.slice(i2) : l1.slice(i1)
  return result.concat(rest)
}

function mergeSort(list) {
  if (list.length <= 1) return [...list]
  let mid = Math.floor(list.length / 2)
  return merge(mergeSort(list.slice(0, mid)), mergeSort(list.slice(mid)))
}

三、冒泡排序

特点:原地排序,不消耗额外空间来存储待排序的元素。

function bubbleSort (list) {
  for (let i = 0; i < list.length; i++) {
    for (let j = 1; j < list.length - i; j++) {
      list[j] < list[j - 1] && ([list[j - 1], list[j]] = [list[j], list[j - 1]])
    }
  }
}
¥打赏