Scalers点评：成长会的算法小组已经启动，这是3周的学习笔记。
写在前面的话：Algorithms + DataStructures = Programs。程序的运行效率很大程度上取决于程序所采用的算法的性能。如果你想提高自己的编程能力，对程序的运行效率有追求，那么快加入和我们一起学习算法吧。算法小组是成长会内部小组，如果你想和我们一起学习算法，你需要是成长会成员，并且完成相关进群任务，欢迎做完入群任务后发给[S157]激流。
往期日志：
本周学习情况
本周（）学习MITOPENCOURSE上的的第3个和第4个 lecture，并开始第二次线上做题。
笔记汇总
Sorting：
The problem of sorting：
Input
array A[1..n] of numbers
Output
A的一个排列B，B[ 1 ] <= B[ 2 ] <= … <= B[ n ]
example
Input:A =[3,4,5,1,2] Output:B= [1,2,3,4,5]
Insertion-Sort
下面是Insertion-Sort的伪代码:
Insertion-Sort(A,n) for j in range(2,n): Insert A[j] into the right position in A[1..j]其实Insertion-sort一个比较形象的理解就是我们在打扑克的时候我们摸到一张新的牌的时候，向前寻找该插入的位置。
既然A[1..j-1]已经有序，那么我们也可以使用Binary-Search来找到要插入的位置。这样找到插入位置需要O(log(n))，但移动元素还是需要O(n)。
用Binary-Search的时间复杂度为O(nlog(n))次比较，O(n2)的比较。
Merge-Sort
下面是Merge-Sort的伪代码:
Merge-Sort A[1..n] if n ==1: return else: Merge-Sort A[1..n/2] Merge-Sort A[n/2+1..n] Merge(A[1..n/2],A[n/2+1..n])Merge-Sort是基于分治法的思想，递归地排序前一半的数组和后一半的数组，然后再把这两个已经排序后的数组合并。
时间复杂度：
T(n) =2T(n/2) + O(n) (n > 1）
T(n) =O(1) (n = 1)
解递归式可以知道T(n) = O(nlog(n))，但Merge-Sort的空间复杂度为O(n)
Heap
build_max_heap:创建一个最大堆max_heapify:修正一个结点，这个结点违反了Max-Heap的性质insert:插入一个结点
extract_max: 找出heap中的最大值
Heap是优先级队列的一种实现方式。
Heap形式上像array，但实际上又是一棵树。
Max-Heap的性质：一个Node的key >= 它的孩子结点的key。
下面是一个Max-Heap的例子：
Heap的高度是O(log(n))
Max-Heap的一些重要操作：
Heap-Sort(有6个步骤，顺序如下：):
Heap-Sort的时间复杂度为O(nlog(n))，空间复杂度为O(1)
从array中建一个最大堆
找到最大值A [ 1 ]
A[ n ]和A[ 1 ]交换，这样A[ n ]就是数组的最大值
把A[ n ]从heap中删除
在根结点处调用
max_heapify维护堆的性质回到步骤2除非堆已经空了
线上做题leetcode
[. Merge Two Sorted Lists][https://leetcode.com/problems/merge-two-sorted-lists/]
[.Remove Duplicates from Sorted List][https://leetcode.com/problems/remove-duplicates-from-sorted-list/]
第一道题目是把两个有序链表合并，有点像Merge-Sort里面的merge部分，只是Merge-Sort里面是对两个有序数组进行merge，而这里是链表，当然操作会略有不同。
第二道题目也是链表类的题目，是在一个有序链表中把重复元素删掉。这个需要用到双指针法。
ScalersTalkID:scalerstalk
本微信公众号作者Scalers，游走在口译世界的IT从业者。微信公众号ScalersTalk，网站ScalersTalk.com，口译小时训练计划群C
成长会是由Scalers发起的面向成长、实践行动，且凝聚了来自全球各地各行各业从业者的社群。有意入会者请和Scalers直接联系，我和其他会员会和你直接交流关于成长行动等各方面的经验教训。年成长会持续招募中，参见做能说会写的持续行动者：ScalersTalk成长会年会员全球招募