Bubble sort

后面的数据是有序的，所以要找出较大的值，然后前后进行调换。需要进行多次循环比较，所以时间复杂度是O(n2)，要进行内外双层循环操作。

  1. function bubbleSort (arr) {
  2.     for (let i = 0; i < arr.length; i++) {
  3.       for (let j = 0; j < arr.length - i - 1; j++) {
  4.         if (arr[j] > arr[j + 1]) {
  5.         // 保存较大的数据
  6.           const temp = arr[j]
  7.         arr[j] = arr[j + 1]
  8.         arr[j + 1] = temp
  9.       }
  10.     }
  11.   }
  12.   return arr
  13. }

Selection sort

前面的数据是有序的，后面的数据是无序的，每次都找到数组中最小的数据，然后将其移到前面的有序列。min 保存的是最小数据的角标，i 是当次循环中的第一个数据，也是此次循环的第一个位置。将最小的数据放置到角标最小的位置。时间复杂度是O(n2)。

  1. function selectionSort (arr) {
  2.     for (let i = 0; i < arr.length; i++) {
  3.       let min = i
  4.     for (let j = i + 1; j < arr.legnth; j++) {
  5.         if (arr[j] < arr[min]) {
  6.           min = j
  7.       }
  8.     }
  9.     const temp = arr[i]
  10.     arr[i] = arr[min]
  11.     arr[min] = temp
  12.   }
  13.   return arr
  14. }

Insertion sort

前面的数据是有序的，后面的数据是无序的。每一次拿出一个数据，与前面的有序数据进行对比，然后将其插入到合适的位置。temp 中始终存最小的数据，可以通过改变角标的值来进一步控制对应的数据值。时间复杂度是O(n2)。

  1. function insertionSort (arr) {
  2.     for (let i = 1; i < arr.length; i++) {
  3.       const temp = arr[i]
  4.     let j = i - 1
  5.     while (j >= 0 && temp < arr[j]) {
  6.         arr[j + 1] = arr[j]
  7.       j--
  8.     }
  9.     arr[j + 1] = temp
  10.   }
  11.   return arr
  12. }

Merge sort

归并排序先将数组从中间进行分割，然后再进行合并。即先分割，再合并。时间复杂度为O(nlog n)。

  1. const merge = (left, right) => {
  2.     let temp = []
  3.   let leftIndex = 0
  4.   let rightIndex = 0
  6.   while (left.length > leftIndex && right.length > rightIndex) {
  7.       if (left[leftIndex] <= right[rightIndex]) {
  8.         temp.push(left[leftIndex])
  9.       leftIndex++
  10.     } else {
  11.         temp.push(right[rightIndex])
  12.       rightIndex++
  13.     }
  14.   }
  15.   return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
  16. }
  18. const mergeSort = (arr) => {
  19.     if (arr.length <= 1) return arr
  20.   const middle = Math.floor(arr.length / 2)
  21.   const left = arr.slice(0, middle)
  22.   const right = arr.slice(middle)
  24.   return merge(mergeSort(left), mergeSort(right))
  25. }

Quick sort

快排采用递归的方式来进行排序，先找一个中点值，小于此值的放到左侧数组，大于此值的放到右侧数组，然后再对左右两个数组进行递归排序。最后将两者连接到一起。时间复杂度为O(nlog n)。

  1. function quickSort (arr) {
  2.     if (arr.length <= 1) {
  3.       return arr
  4.   }
  5.   const pivot = arr[0]
  6.   const left = []
  7.   const right = []
  8.   for (let i = 1; i <= arr.length; i++) {
  9.       if (arr[i] < pivot) {
  10.         left.push(arr[i])
  11.     } else {
  12.         right.push(arr[i])
  13.     }
  14.   }
  15.   return quickSort(left).concat(pivot, quickSort(right))
  16. }