TIP

算法与数据结构小记

数据结构

数据的逻辑结构

线性结构

一维数组

栈

先进后出

栈的应用：表达式求值、括号匹配、递归

队列

先进先出

队列的应用：打印队列

• 循环队列
• 双端队列（若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈）

串

仅由字符构成的有限序列

• 空串：长度为零的串称为空串，空串不包含任何字符

• 空格串：由一个或多个空格组成的串

• 子串：由串中任意长度的连续字符构成的序列称为子串。 含有子串的串称为主串。空串是任意串的子串。

非线性结构

多维数组

树

• 二叉树

  1. 前序遍历（根左右）

  2. 中序遍历（左根右）

  3. 后序遍历（左右根）

• 二叉查找树（二叉排序树）

  1. 若它的左子树非空，则左子树上所有结点的值均小 于根结点。
  2. 若它的右子树非空，则右子树上所有结点的值均大 于根结点。
  3. 左、右子树本身又各是一棵二叉排序树。

• 哈夫曼树

  给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路 径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的 结点离根较近。

图

数据的存储结构

顺序存储

链式存储

• 单链表
• 单向循环链表
• 双链表
• 双向循环链表

索引存储

散列存储

算法

经典算法思想

• 分治法：将复杂问题分解成若干规模相同的子问题。
• 贪心法：不从整体考虑只求当前局部最优解。
• 回溯法：达不到（最优）目标，就退回再走。
• 动态规划：类似于分治法。但具有最优子结构性质和重叠子问 题性质。

一、查找算法

1、顺序查找

将待查的元素从头到尾与表中元素进行比较， 如果存在，则返回成功；否则，查找失败。此方法效率不 高。 平均查找长度： （n+1）/2

/*
 * @param {Array} arr
 * @param {} key 待查元素
 */
function sequenceSearch(arr, key) {
  let len = arr.length;
  for( let i=0; i<len; i++) {
    if(arr[i] === key) return i;
  }
  return -1; // 查找失败
}
// 时间复杂度： O(n)

// 哨兵顺序查找

function sequenceSearch(arr, key) {
  let len = arr.length;
  let i = 0;
  arr.push(key);

  while(arr[i] !== key) {
    i++;
  }
  if(i===arr.length) return -1;
  return i;
}
// 时间复杂度 O(n)

// 普通顺序查找 每次循环需要两个判断 i<len 和 arr[i]===key
// 哨兵顺序查找 每次循环只需要一个判断 arr[i]!==key, 保证会有一个相等不用判断边界;数据量大的时候差距越明显

2、二分查找法

二分查找法前提是元素是有序的（一般为升序）

/*
 * 查找元素key在arr中的下标，不存在则返回-1
 * @param {Array} arr
 * @param {} key 待查元素
 * @param {Number} lowIndex 查找区间 低位下标
 * @param {Number} highIndex 查找区间 高位下标
 */
function halfSearch(arr, key, lowIndex, highIndex) {
  let mid = Math.floor((highIndex+lowIndex)/2);
  if(lowIndex === highIndex && arr[mid]!==key) return -1;
  if(arr[mid]>key) {
    return halfSearch(arr, key, lowIndex, mid-1);
  } else if(arr[mid]<key) {
    return halfSearch(arr, key, mid+1, highIndex);
  } else {
    return mid;
  }
}

function halfSearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while(start <= end) {
    let mid = Math.floor((start+end)/2);
    let a = arr[mid];
    if(a === target) return mid;
    if(a<target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

// 时间复杂度 O(log(n))

4、哈希查找法

二、排序算法

1、直接插入排序

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序

// arr

function insertSort(arr) {
  let len = arr.length;
  if(len < 2) return arr;
  let i = 1; // 有序列表的终止下标
  while(i<len) {
    for(let j=i-1; j>=0; j--) {
      if(arr[j+1]<arr[j]) {
        [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
      }
    }
    i++;
  }
  return arr;
}

// 时间复杂度 O(n^2)

2、冒泡排序

每次循环都将最大值冒泡到后面， 排序是从数组后往前排

function bubbleSort(arr) {
  let len = arr.length;
  if(len < 2) return arr;
  for(let i=0; i<len; i++) {
    for( let j=0; j<len-i-1; j++) {
      if(arr[j]>arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

// 时间复杂度 O(n^2)

3、简单选择排序

每次选出最小值

function selectSort(arr) {
  let len = arr.length;
  if(len < 2) return arr;
  let i = 0; // 关键字下标
  while(i<len) {
    let min = i; // 从关键字下标开始的最小值下标
    for(let j=i+1; j<len; j++) {
      if(arr[min]>arr[j]) {
        min = j;
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]];
    i++
  }
  return arr;
}

// 时间复杂度 O(n^2)

4、希尔排序

先将整个待排元素序列分割成若干个子序列（由相隔某个“增”的元素组 成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列 中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高 的。 先取一个小于n的整数d1，作为第一个增量，把文件的全部记录分成d1个 组，即将所有距离为d1倍数序号的记录放在同一个组中，在组内进行直接插 入排序；然后取第二个增量d2＜d1，重复上述步骤，依次类推，直到所取 的增量di=1,即将所有记录放在同一组进行直接插入排序。

function shellSort(arr) {
  let len = arr.length;
  if(len < 2) return arr;

  for(let delta = Math.floor(len/2); delta>0; delta = Math.floor(delta/2)) {
    for(let i= 0; i<delta; i++) {
      let j = i;
      // 直接插入排序
      let key = arr[i];

      while(j+delta<len && key > arr[j+delta]) {
        arr[j] = arr[j+delta];
        j+=delta;
      }
      arr[j] = key;
    }
  }
  return arr;
}

// 时间复杂度 O(n^1.3)

5、快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一 趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两 部分数据分别进行快速排序，整个排序过程可以递归进行，以此 达到整个数据变成有序序列。

function fastSort(arr) {
  let len = arr.length;
  if(len<2) return arr;
  let mid = 0;
  let left = [];
  let right = [];

  for(let i=1; i<len; i++) {
    if(arr[i]<arr[mid]) {
      left.push(arr[i])
    } else {
      right.push(arr[i]);
    }
  }
  return fastSort(left).concat(arr[mid], fastSort(right));

}
// 时间复杂度 O(nlogn)

6、归并排序

1. 分解。将n个元素分层各含n/2个元素的子序列
2. 求解。用归并排序对两个子序列递归地排序
3. 合并。合并两个已经排好序的子序列以得到排序结果。

function mergeSort(arr) {
  let len = arr.length;
  if(len < 2) return arr;
  let mid = Math.floor(len/2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  function merge(left, right) {
    let r = [];
    let i = 0;
    let j = 0;
    while(i<left.length&&j<right.length) {
      if(left[i]<right[j]) {
        r.push(left[i]);
        i++;
      } else {
        r.push(right[j]);
        j++;
      }
    }

    while(i<left.length) {
      r.push(left[i]);
      i++
    }
    while(j<right.length) {
      r.push(right[j]);
      j++
    }

    return r;
  }

  return merge(mergeSort(left), mergeSort(right));
}

// 时间复杂度 O(nlogn)

7、堆排序

满足 Ki >= 2Ki && Ki >= 2Ki +1 大顶堆 或 Ki <= 2Ki && Ki <= 2Ki +1 小顶堆