几种排序算法-Yinode Blog

冒泡排序

冒泡排序顾名思义，就是将一个个数字冒泡一样的推送到他该去的地方。

冒泡算法的核心内容其实就是比较相近的两个值，如果前值大于后值，就进行交换。

代码

function bubbleSort(arr) {
  let len = arr.length
  for (let i = 0; i < len - 1; i++) {
    // 最末位已经完成排序，所以不需要额外的计算
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
    }
  }
  return arr
}

冒泡可以说是最为简单的排序算法了，唯一值得注意的就是迭代次数，在外层的时候其实只需要length - 1就可以了，第二层则因为末尾是排序完成的部分，不需要比较所以 - i - 1

算法复杂度

O(n^2) 稳定

选择排序

选择排序的核心思想是每次将最小的值与当前目标值进行交换

代码


function selectSort(arr) {
  let len = arr.length
  for (let i = 0; i < len - 1; i++) {
    // 区间内的最小值 将会不断更新
    let index = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[index]) {
        // 如果后续发现有值小于arr[i] 则更新index
        index = j
      }
    }
    // swap交换
    let temp = arr[index]
    arr[index] = arr[i]
    arr[i] = temp
  }
  return arr
}

同样，选择排序也是非常简单的一种排序方法，但他本身的算法复杂度也不容乐观

算法复杂度

O(n^2) 并且不稳定

插入排序

插入排序有点类似于你打扑克牌，将一张无序的牌插入到一堆有序的序列之中。

代码

function insertSort(arr) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    // temp其实就是拿出来准备插入的牌
    // 也就是每次从未排序的牌中拿出一张，插入到排序完成的牌堆中
    let temp = arr[i]
    // j 循环的是已经排序完成的手牌
    for (let j = 0; j < i; j++) {
      if (temp < arr[j] && j === 0) {
        arr.splice(i, 1)
        arr.unshift(temp)
        break
      } else if (temp < arr[j + 1] && temp >= arr[j]) {
        arr.splice(i, 1)
        arr.splice(j + 1, 0, temp)
        break
      }
    }
  }
  return arr
}

值得注意的就是必须break否则可能会出现相同值被多次插入的问题

复杂度

O(n^2) 稳定

快速排序

快速排序其实是一种分治法的思想，每次选出一个中点下标，通过比较来划分left right两个数组，递归运行

代码

function quickSort(arr) {
  if (arr.length <= 1) return arr

  let pirvotIndex = Math.floor(arr.length / 2)
  let pirvot = arr.splice(pirvotIndex, 1)[0]

  let left = []
  let right = []

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

感觉快排真是排序算法中的高富帅阿，跑得又快，长的还帅，看起来就很俊阿

复杂度

O(nlogn）不稳定

归并排序

归并排序要使用了分治法的思想，他建立在如何合并两个已经排序完成的数组这一问题上，把整个数组拆分成小的排序完成的数组（最小的粒度其实每一个值都是一个数组），然后进行合并。

代码

function mergeSort(arr) {
  let len = arr.length
  // seg 可以被认为是层级 1 2 4 8 16 不断的从琐碎的层级往上层合并
  for (let seg = 1; seg < len; seg += seg) {
    let arrb = []
    for (let start = 0; start < len; start += 2 * seg) {
      // start mid high其实就是分割两个有序数组的三个必须下标点
      const mid = Math.min(start + seg, len)
      const high = Math.min(start + 2 * seg, len)

      let start1 = start,
        end1 = mid
      let start2 = mid,
        end2 = high
      // 两者都具有元素的情况，比较两个有序数组的头第一个值，小的先进
      while (start1 < end1 && start2 < end2) {
        arr[start1] < arr[start2] ? arrb.push(arr[start1++]) : arrb.push(arr[start2++])
      }
     // 一方全部进去了  剩下的一方不需要比较 直接进
      while (start1 < end1) {
        arrb.push(arr[start1++])
      }
      while (start2 < end2) {
        arrb.push(arr[start2++])
      }
    }
    arr = arrb
  }
  return arr
}

基数排序

基数排序本身是一种统计排序，就是将数的每一位进行一次排序，最终返回一个正常顺序的数组。从宏观上看，他有点安排的感觉，把一系列的值计算他的位置，然后安排上去

代码

function radixSort(arr) {
  const len = arr.length
  let dis = 0
  let tmp = new Array(len)
  let count = new Array(10)
  let maxNum = Math.max(...arr)
  while (maxNum >= 1) {
    maxNum /= 10
    dis++
  }

  for (let i = 0, radix = 1; i < dis; i++) {
    for (let j = 0; j < 10; j++) {
      count[j] = 0
    }
    for (let j = 0; j < len; j++) {
      let k = parseInt(arr[j] / radix) % 10
      count[k]++
    }
    for (let j = 1; j < 10; j++) {
      count[j] += count[j - 1]
    }
    // !! 注意 必须是j从末尾开始循环 不然顺序会被破坏
    for (let j = len - 1; j >= 0 ; j--) {
      let k = parseInt(arr[j] / radix) % 10
      tmp[count[k] -1] = arr[j]
      count[k]--
    }
    for (let j = 0; j < len; j++) {
      arr[j] = tmp[j]
    }
    console.log(arr);
    radix *= 10
  }
  return arr
}

几种排序算法

TOC