• 第一章 算法简介
  • 二分查找
  • 大O表示法
  • 小结
• 第二章 选择排序
  • 数组和链表
  • 选择排序
• 第三章 递归
  • 基线条件和递归条件
  • 栈
  • 小结
• 第四章 快速排序
  • D&C分而治之
    • 步骤
    • 特征
  • 快排算法
  • 再谈大O表示法
    • 合并排序（归并排序）
  • 小结

大O表示法，递归与D&C

第一章 算法简介

二分查找

1. 前提：已排序
2. 方式：在有序列表中逐次取中间项(或某一项)的值，获取与目标值的大小比较信息，做排除。

   def binary_search(list, item):
    low = 0
    haight = len(list) - 1
    while(low <= high):
        mid = (low + high)/2
        guess = list[mid]
        if guess < item:
            low = mid + 1
        elif guess > item:
            high = mid - 1
        elif guess == item:
            return mid
    return None
   

大O表示法

• 大O表示法指出了算法运行时间（随元素数）的增速，可让你比较方便的比较达到目的的（所需的）操作（次）数。
• 常见大O表示法运行时间：

注：log为log2

小结

• 二分查找的速度比简单查找快得多。
• O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快的多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度衡量的。
• 算法运行时间用大O表示法表示。

第二章 选择排序

数组和链表

1. 数组在内存中是连续的
2. 链表中的元素可存储在内存的任何位置，链表中的每个元素都存储了下一个元素的地址。
3. 数组的读取速度很快（因为可按索引直接取值，而链表要顺序查找）。
4. 链表的插入和删除速度很快（因为链表只需要改两个指向的指针，而数组需要重新排改动元素后的所有元素的索引）。

选择排序

一个逐项遍历找当前最大值(或最小值)的排序算法，每次遍历时间为O(n)，需遍历n次。(找出最大的，找出第二大的，找出第三大的…)

第三章 递归

基线条件和递归条件

1. 基线条件：指函数不再调用自己的条件，即退出递归的条件。
2. 递归条件：函数调用自己的条件。

栈

1. 递归的本质是压栈和出栈，当然函数的调用也是。
2. 递归层深可能会占用大量内存，引起溢出。
3. 使用尾递归，大部分语言都是有尾递归优化的。

小结

• 递归指的是调用自己的函数。
• 每个递归函数都有两个条件，基线条件和递归条件。
• 栈有两种操作：压入和弹出。
• 所有函数调用都进入调用栈。
• 调用栈可能很长，这将占用大量内存。

第四章 快速排序

D&C分而治之

divide and conquer

步骤

• 找出基线条件
• 分解成子问题

特征

• 通过分解到一定程度可以轻松解决
• 分解为的子问题具有最优子结构性质
• 分解出的子问题可以合并为该问题的解。
• 分解出的子问题互斥

快排算法

找一项的值为基准值，将元素与基准值按大小关系分为左分区和右分区，并在左分区和右分区做重复操作，直至分区只有一项（分而治之），然后合并所有（单项）子分区。

• 基线条件 length<2不需要排序
• 将数组拆为一个个length<2的数组
• 合并

function quickSort (arr) {
  if (arr.length < 2) {
    return arr
  }
  let baseValue = arr.splice(arr.index - 1, 1)
  let left = []
  let right = []
  arr.forEach(item => {
    if(item > baseValue) {
      right.push(item)
    } else {
      left.push(item)
    }
  })
  return quickSort(left).concat(baseValue, quickSort(right))
}

再谈大O表示法

最糟情况下，快排运行时间为O(n^2)（基准值选取最边缘值会导致无法进行拆分），平均情况下为O(nlogn)。 合并排序的运行时间总为O(nlogn)

合并排序（归并排序）

将待排序列逐层拆分，直到成为单个项，并逐层两两合并，合并时比较第一项的大小并放入新的数组(同样是分而治之)。

[0, 8, 1, 3, 4, 7]
         ↓        
[0, 8, 1] [3, 4, 7]
         ↓
[0] [8, 1] [3] [4, 7]
         ↓
[0] [8] [1] [3] [4] [7]
         ↓
[0, 8] [1, 3] [4, 7]
// 合并 [0, 8] [1, 3],每次取索引为0的值最小的项
// (1)：[0] [8] [1, 3] [4, 7]
// (2)：[0, 1] [8] [3] [4, 7]
// (3)：[0, 1, 3] [8] [] [4, 7]
// (4)：[0, 1, 3, 8] [4, 7]
         ↓
[0, 1, 3, 8] [4, 7]
// (1)：[0] [1, 3, 8] [4, 7]
// (2)：[0, 1] [3, 8] [4, 7]
// (3)：[0, 1, 3] [8] [4, 7]
// (4): [0, 1, 3, 4] [8] [7]
// (5): [0, 1, 3, 4, 7] [8]
// (6): [0, 1, 3, 4, 7, 8]
         ↓
[0, 1, 3, 4, 7, 8]

Array.prototype.mergeSort = function() {
  function merge(left, right) {
    var final = []
    while (left.length && right.length)
      final.push(left[0] <= right[0] ? left.shift() : right.shift())
    return final.concat(left.concat(right))
  };
  var len = this.length
  if (len < 2) return this
  var mid = parseInt ( len / 2 )
  return merge(this.slice(0, mid).mergeSort(), this.slice(mid).mergeSort())
};

小结

• D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
• 实现快速排序时，请随机的选择用作基准值的元素。快速排序的平均运行时间为O(nlogn)。
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(logn)的速度比O(n)快的多。