排序算法

---

插入排序

即用i遍历数组，假设1到i-1为有序数组，每次将i往前搜索，找到它应该插入的位置j，将之前的a[j]到a[i-1]往后移一位，即移到a[j+1]到a[i]，算法复杂度为O(N^2)，是一种稳定的排序法（什么是稳定的排序法？，稳定排序就是说假设两个相同的元素，那么排序之后他们的前后关系是否保持不变，不变就是稳定的，否则是不稳定的。）

---

冒泡排序：

依次比较相邻的两个数，如果顺序不同则交换，每次遍历一遍可以使最后的数为当前最大的，那么做n-1遍就可以将所有的数都排好序。是一种稳定排序法。

---

堆排序：

即建立大根堆或者小根堆，建堆的时间复杂度为O(N)，证明在这里，然后每次取出堆顶元素，进行调整，时间复杂度为O(NlogN)，是不稳定的排序方法。

---

快速排序：

即用二分的方法递归对数组进行排序，是不稳定的排序方法。时间复杂度是O(NlogN)

---

归并排序：

分为两种，递归的和非递归的，是稳定的排序方法。时间复杂度是O(NlogN)

---

大师定理

证明：见算法导论93页，网上证明

---

基于比较的排序算法的下界证明

基于比较的排序最好情况是Ω(NlogN)通过决策树证明：一共有N!个叶子，因为N个数一共有N!种排列，所以最深的地方深度为logN! = Ω(NlogN)，所以最好的排序就是这个复杂度。

---

最短路径

---

Dijkstra’s Algorithm:

初始化：所有节点到源节点的距离设为无穷，源节点到自己的距离为0。

迭代N次：初始选择源节点，更新所有和源节点相邻的节点。然后依次选择剩下的没被标记的节点当中离源节点最近的节点，直到所有节点都被标记。

时间复杂度：(用二叉堆 vs 队列)

二叉堆：O((V+E)*logV)

队列: O(V^2)

---

斐波那契堆（见算法导论526页）

---

编辑距离

从一个字符串都另外一个字符串的距离，即通过多少次增加、删除、替换的操作可以从A字符串变成B字符串。
动态规划转移方程：

E(i,j) = min{1+E(i-1,j), 1+E(i,j-1), diff(i,j)+E(i-1,j-1)}

时间复杂度为O(m*n)