1. 快速排序

原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

实现步骤：

  • 选择一个基准元素target（一般选择第一个数）；
  • 将比target小的元素移动到数组左边，比target大的元素移动到数组右边；
  • 分别对target左侧和右侧的元素进行快速排序；

从上面的步骤中我们可以看出，快速排序也利用了分治的思想（将问题分解成一些小问题递归求解）选择一个基准元素target（一般选择第一个数）

  1. function quickSort(array) {
  2.   if (array.length === 1) return array
  3.   const target = array[0]
  4.   const left = []
  5.   const right = []
  6.   for (let i = 0; i < array.length; i++) {
  7.     if (array[i] < target) {
  8.       left.push(array[i])
  9.     } else {
  10.       right.push(array[i])
  11.     }
  12.   }
  13.   return quickSort(left).concat([target], quickSort(right))
  14. }
  • 时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)；
  • 空间复杂度：O(logn)（递归调用消耗）

2. 冒泡排序

原理：循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。这样一次循环之后最后一个数就是本数组最大的数。下一次循环继续上面的操作，不循环已经排序好的数。

优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环。

  1. function bubbleSort(array) {
  2.   for (let j = 0; j < array.length; j++) {
  3.     let complete = true
  4.     for (let i = 0; i < array.length - 1 - j; i++) {
  5.       if (array[i] > array[i+1]) {
  6.         [array[i], array[i+1]] = [array[i+1], array[i]]
  7.         complete = false
  8.       }
  9.     }
  10.     if (complete) {
  11.       break
  12.     }
  13.   }
  14.   return array
  15. }
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)