派大星

function bubbleSort(array) {
      for (let j = 0; j < array.length; j++) {
        let complete = true;
        for (let i = 0; i < array.length - 1 - j; i++) {
          // 比较相邻数
          if (array[i] > array[i + 1]) {
            [array[i], array[i + 1]] = [array[i + 1], array[i]];
            complete = false;
          }
        }
        // 没有冒泡结束循环
        if (complete) {
          break;
        }
      }
      return array;
    }

# 复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

# 5、选择排序

每次循环选取一个最小的数字放到前面的有序序列中。

# 解法

 function selectionSort(array) {
      for (let i = 0; i < array.length - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < array.length; j++) {
          if (array[j] < array[minIndex]) {
            minIndex = j;
          }
        }
        [array[minIndex], array[i]] = [array[i], array[minIndex]];
      }
    }

# 复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

# 大O记法忽略常数

选择排序的步数大概只有冒泡排序的一半，即选择排序比冒泡排序快一倍。

但是严格来说选择排序应为 O(N2 / 2)，最终得写成 O(N2 )。

类似地，O(2N)要写成 O(N)； O(N / 2)也写成 O(N)；就算是比 O(N)慢 100 倍的 O(100N)，也要写成 O(N)。

# 6、插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

function insertSort(array) {
      for (let i = 1; i < array.length; i++) {
        let target = i;
        for (let j = i - 1; j >= 0; j--) {
          if (array[target] < array[j]) {
            [array[target], array[j]] = [array[j], array[target]]
            target = j;
          } else {
            break;
          }
        }
      }
      return array;
    }

# 复杂度

时间复杂度：O(n2)

空间复杂度:O(1)

# 7、快速排序

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

先从右往左找一个小于 基准值 的数，再从左往右找一个大于 基准值 的数，然后交换他们。

这个图解很清楚：算法 3：最常用的排序——快速排序 (opens new window)

实现步骤：

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

简单版本

function quickSort(array) {
      if (array.length < 2) {
        return array;
      }
      const target = array[0];
      const left = [];
      const right = [];
      for (let i = 1; i < array.length; i++) {
        if (array[i] < target) {
          left.push(array[i]);
        } else {
          right.push(array[i]);
        }
      }
      return quickSort(left).concat([target], quickSort(right));
    }

# 8、数据结构

链表（带有存储下一个结点地址的）插入和删除效率比数组高很多

# 9、空间复杂度

空间复杂度：当所处理的数据有 N 个元素时，该算法还需额外消耗多少元素大小的内存空间

O(1)：记住，时间复杂度的O(1)意味着一个算法无论处理多少数据，其速度恒定。相似地，空间复杂度的 O(1)则意味着一个算法无论处理多少数据，其消耗的内存恒定。

派大星