基础算法总览复习

最近正在上左神的算法基础课，左神讲的非常透彻，重要的还是课下把课上讲的和作业的自己实现并且加以复习。

这篇复习集（姑且取个名字）总结下个人在这段时间学习到的算法topics，这样方便我以后回来复习。

---

¶排序 Sort

直接上干货

Sort Algorithm

Time Complexity

Space Complexity

Stability

Selection Sort

O(N²)

O(1)

False

Bubble Sort

O(N²)

O(1)

True

Insertion Sort

O(N²)

O(1)

True

Merge Sort

O(N*logN)

O(N)

True

Heap Sort

O(N*logN)

O(1)

False

Quick Sort

O(N*logN)

O(logN)

False

Bucket Sort

O(N)

O(N)

True

归并排序，堆排序，和快速排序是最快并且最方便使用的三种排序。根据需求选择需要的排序算法。

桶排序包括了 计数排序和基数排序，桶排序尽管很快但是对数据状况有要求，例如计排要求数据状况处于一个相对窄的域，基数排序要求样本都为十进制数

对于使用递归调用的排序算法可利用Master Theorem分析时间复杂度：

适用于子过程（subprocess）缩小的规模都是 n/b，调用a次subprocess（且都是等规模地缩小），加上其他的 f(n) 或者 可以表示为 O(n^d)的 时间操作。

这样就能细分为三种情况：

• log b (a) < d => O(n^d)
• log b (a) > d => O(n^(log b (a)))
• log b (a) = d => O(n^(d) * log(n))

快排：不追求稳定性，指标最优，常数最优。
堆排：追求更少的额外空间复杂度。
归并：追求稳定性。

¶排序相关练习题目

• 局部最小： arr无序，相邻不相等，返回任意一个局小index
• 提出奇次数：arr中只有一个数出现了奇数次，其余为偶数次，找到这个数
  • 拓展：有两个数出现奇数次，其余为偶数次，找到这两数
• 小和（small sum）：arr中一个数左边比当前数小的数累加起来，叫做这个数组的小和，求arr 的小和
• 逆序对：一个arr中左边的数如果比右边的数大，则这两个数构成逆序对，打印所有逆序对
• 几乎有序的数组，每个元素排好序最多不移动k距离，求最好的排序算法排序
• 荷兰国旗

---

¶链表 Linked List 和

¶哈希表（字典）Hash Table

单链表和双向链表是重要的数据结构

关于链表， 基础的问题有：

• 反转单向链表和双向链表
• 打印两个有序链表的公共部分

进阶一点的问题有：

• 判断一个链表是否为回文结构（palindrome）
• 复制含有随机指针节点的链表
• 两个单链表相交的问题