数据结构与算法

基础数据结构

1.1数组

一个含有数据的列表

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"]

了解某个数据结构（例如数组）的性能，得分析程序怎样操作这一数据结构。
一般数据结构有四种操作

• 读取 (查找数据中指定索引处的值， array[0])
• 查找 (从数据结构中找出某个数据值的所在)
• 插入
• 删除

重要理论：操作的速度，并不按时间计算，而是按步数计算
此外，操作的速度，也被成为称为 时间复杂度

每种操作所用的步数

• 读取：一步，计算机本身就有跳到任一索引位置的能力。
• 查找：从索引0处开始，一个一个去对比查找，这种也被称为线性查找，对于长度为 N 的数组，其线性查找的最多步数为 N
• 插入：如果向数组的末尾插入，只需要一步，如果在开头或者中间插入，需要先将后边部分的数据一步一步向右挪，最后插入，所以需要额外的步数
• 删除： 看起来删除，只需要一步，但实际上，删除之后，需要将后面的数据往前挪，补齐删掉的地方。

1.2 集合： 一条规则决定性能

一种不允许元素重复的数据结构。

和数组相比，集合的查找与删除操作所需的步数是相同的，但对于插入，集合需要先确定是否存在值，因为它不能有重复的值

2.1 二分查找：对于有序数组的查找方法

对于从小到大排列的数组，从中间开始，比较所查找值的大小，如果小于中间值，则排除右侧，否则排除左侧
对于长度大的数据，二分查找比线性查找更具有优势
二风查找的大O记法为O(log N)

O(log N)

时间复杂度叫作对数时间
当数据量翻倍时，步数加1

大O记法

方便表达数据结构和算法的时间复杂度
不关注算法所用时间，只关注步数
忽略常数，在选择排序里面，效率实际上是O(N^2 / 2),但仍表示为O(N^2)
大 O 只保留最高阶的N

表示方法

如，数组不论多大，读取都只需 1 步。
表示为：O(1)
对于 N 个元素的数 组，线性查找需要花 N 步。
表示为：O(N)

线性时间与常数时间

O(N)也被称为线性时间。
O(1)被称为常数时间。

冒泡排序

let array = [3, 13,2, 8, 4, 34, 53, 22]
let c

for (let i = 0;i < array.length-1; i++) {
  for (let j = i+1; j+i+1<array.length; j++) {
    if (array[i] > array[j]) {
      c = array[i];
      array[i] = array[j]
      array[j] = c;
    }
  }
}

效率: O(N^2)
一般嵌套循环算法的效率就是 O(N^2)

选择排序

let array = [9, 2, 6, 3, 1]

for (let i=0; i<array.length-1; i++) {
  let lowNumIndex = i;
  for (let j=i+1;j<array.length; j++ ) {
    if (array[i] < array[lowNumIndex]) {
      lowNumIndex = j;
    }
  }
  
  if (lowNumIndex != i) {
    let temp = array[i];
    array[i] = array[lowNumIndex]
    array[lowNumIndex] = temp
  }
}

效率为：O(N^2)
但选择排序比冒泡排序快一倍

插入排序

let array = [2, 8, 3, 1, 5]

for (let i=1; i<array.length; i++) {
  let p = i
  let temp = array[i]
  
  while (p > 0 && array[p-1] > temp) {
    array[p] = array[p-1]
    p = p-1;
  }
  array[p] = temp
}