前言

学习排序算法是大一下学期上数据结构课的时候的事了，当时学习用的是c++，如今javascript已经成了我的主语言。为了准备面试和巩固基础，我决定用js写一遍10大排序算法并且上传到博客，算是复习一遍基础的算法吧。

冒泡排序（Bubble Sort）

算法描述

使用冒泡排序为一列数字进行排序的动态效果图

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let bubble_sort = (array) => {
  let length = array.length
  for (let i = 0; i<length-1; i++) {
    for (let j = 0; j<length-1-i; j++) {
      if (array[j]>array[j+1]) {
        // 这里用了es6的解构赋值， 不用创建一个临时的变量来存放值
        [array[j], array[j+1]] = [array[j+1], array[j]]
      }
    }
  }
  console.log(array)
  return array
}

let num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
bubble_sort(num)

一个冒泡排序的例子动画

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
冒泡排序 n n² n² 1 是

[^是否稳定]: 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面； 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面

选择排序（Selection Sort）

算法描述

动态效果图

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let selection_sort = (array) => {
  let length = array.length
  // 定义一个值来记录每一次循环得到的最小值的下标
  let minIndex
  for (let i = 0; i<length-1; i++) {
    minIndex = i
    // 通过本次循环得到从i+1开始的数组的最小值
    for(let j = i+1; j<length; j++) {
      if (array[j]<array[minIndex]) {
        minIndex = j
      }
    }
    // 将最小值换到数组前面
    [array[i], array[minIndex]] = [array[minIndex], array[i]]
  }
  console.log(array)
  return array
}

selection_sort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70])

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
选择排序 n² n² n² 1 否

插入排序（Insertion Sort）

算法描述

动态效果

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let insertion_sort = (array) => {
  let length = array.length
  for(let i=1; i<length; i++) {
    console.log(array[i])
    let key = array[i]
    let j = i-1
    while (j>=0 && array[j]>key) {
      array[j+1] = array[j]
      j--
    }
    array[j+1] = key
  }
  console.log(array)
  return array
}

insertion_sort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70])

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
插入排序 n n² n² 1 是

希尔排序（Shell Sort）

算法介绍

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法描述

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1

  • 按增量序列个数k，对序列进行k 趟排序

  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let shell_sort = (array) => {
  for(let gap = array.length>>1; gap>0; gap>>=1) {
    for(let i = gap; i<array.length; i++) {
      let temp = array[i],j
      for(j = i-gap; j>=0 && array[j]>temp; j-=gap) {
        array[j+gap] = array[j]
      }
      array[j+gap] = temp
    }
  }
  console.log(array)
  return array
}
shell_sort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70])

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
希尔排序 nlog(n) n (log(n))2 无法确定 1 否

归并排序

算法介绍

动态效果

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为{\displaystyle O(n\log n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer)的一个非常典型的应用，且各层分治递归可以同时进行。

算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列

  • 对这两个子序列分别采用归并排序

  • 将两个排序好的子序列合并成一个最终的排序序列

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
let merge_sort = (array) => {
  if (array.length<2) {
    return array
  }
  // 向下取整
  let middle = Math.floor(array.length/2)
  let left = array.slice(0, middle)
  let right = array.slice(middle)
  // 使用递归，把问题规模减小
  return merge(merge_sort(left), merge_sort(right))
}

let merge = (left, right) => {
  let res = []
  // 用一个while循环得出两个数组中的最小元素，将其放入res中
  while (left.length>0 && right.length>0) {
    if (left[0]<right[0]) {
      res.push(left.shift())
    } else {
      res.push(right.shift())
    }
  }
  return res.concat(left, right)
}

console.log(merge_sort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]))

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
归并排序 nlog(n) nlog(n) nlog(n) n 是

快速排序

算法介绍

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目需要O(nlog(n))次比较。在最坏状况下则需要O(n²)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop)可以在大部分的架构上很有效率地达成。

算法实现

首先实现数组的分区代码函数，partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let partition = (array, start, end) => {
  // 定义一个数字pivot作为基准，用pivotIndex来跟踪其位置，用pivotValue来跟踪其值
  let pivotIndex = 0
  let pivotValue = array[end]
  for(let i=0; i<end; i++) {
    // 把所有比基准的值小的元素移到其位置的左边
    if (array[i]<pivotValue) {
      [array[i], array[pivotIndex]] = [array[pivotIndex], array[i]]
      pivotIndex++
    }
  }
  // 最后一步把基准（最后一个元素）与 在pivotIndex位置的值交换
  [array[end], array[pivotIndex]] = [array[pivotIndex], array[end]]
  return pivotIndex
}

在排序的函数中用递归来把大问题划分成若干个小问题，只要这个函数收到一个不为空或有多个元素的数组，则将重复该过程

1
2
3
4
5
6
7
8
9
10
11
12
let quick_sort = (array, start, end) => {
  if (start>=end) {
    return
  }
  let index = partition(array, start, end)
  quick_sort(array, start, index-1)
  quick_sort(array, index+1, end)
  return array
}

console.log(quick_sort([22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70],0,13))

名字 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
快速排序 nlog(n) n² nlog(n) log(n) 否

参考资料

十大经典排序算法总结（JavaScript描述）

javascript-algorithms