CS61b:Week 10

排序算法

将未排序的数组全部添加到一个堆中（最大堆/最小堆）然后逐步取出元素一个个添加到新数组中即可完成排序。
复杂度：
- 添加 $N$ 个元素，每次需要 $O(logN)$ ： $O(NlogN)$
- 同理删除N次： $O(NlogN)$
- 新列表的添加： $\Theta(N)$
- 总： $O(NlogN)+O(NlogN)+\Theta(N)=O(NlogN)$

将原数组看成一个未排序的最大堆，（利用二叉树的数组表示法）
然后将数组从后往前逐步构建最大堆（从底部往头部），即可将原本的无效最大堆转化为有效的最大堆。
通过观察发现，每次从堆中删除的元素总是从新数组的末尾往前添加元素，原数组（最大堆）的末尾元素逐渐减少，因此可以从堆中删除元素放到原数组的末尾，以节省一个新数组（不必创建新数组）
注意使用的数据结构是最大堆，而不是最小堆。最大堆每次删除得到的都是最大值，可以放到数组末尾，而最小堆则不行。
复杂度： $O(NlogN)$

将原数组分成两半边，将各半边分别进行归并排序后合并起来。
原数组不断被拆分，知道数组长度为1则不必进行排序，再逐渐一层层合并起来。
合并操作：
- 目的是将两个已排序的数组合并成一个排列好的新数组，分别创建一个指针分别指向两个数组的头元素，比较两个指针的指向元素，将小的那个元素添加到新数组的末尾，并将其向后推1位（使其指向下一个元素），不断重复直到合并完毕。
- 复杂度： $\Theta(N)$
总复杂度： $O(NlogN)$ ，因为有 $log_{2}N$ 层。
一般是在分割到数组长度足够小时，使用插入排序以优化算法

简单想法：建立一个新数组，遍历原数组的各个元素，将其放在新数组的恰当位置(找到新数组中大于该元素的元素，插入到其前面)
实现思路：给定一个未排序的数组，每次取出其第一个元素，其左边为已排序数组，右边为未排序数组。将该元素向左移动，直到其左边的元素比该元素小，此时已排序数组长度加一，未排序数组长度减一。不断重复此过程，直到排序完毕。
不变性：每次抽出未排序数组的第一个元素时，其左边都是以排好序的数组。
复杂度： $\Omega(N)$ ， $O(N^2)$
插入排序对几乎已经完成排序的数组所需时间较少

核心操作：分区，选择一个元素，使其左边的元素均小等于该元素，其右边的元素均大等于该元素。
随机选择一个元素进行分区后，分成了左右两个数组，于是便可以对两边的数组分别再次进行分区，将一个大问题转化成了相似的小问题。重复上述过程，逐步将大问题转化为若干个小问题，分别解决。
复杂度：
- 最好情况，每次选择作为分区基准点的元素恰好为中间元素，则需花费 $\Theta(N)$ ，共 $\Theta(logN)$ 层，总共 $\Theta(NlogN)$
- 最坏情况，每次选择作为分区基准点的元素位于边缘，则复杂度为 $\Theta(N) \times \Theta(N)=\Theta(N^2)$
- 若是随机选择元素，则可以得到绝大部分都是 $O(NlogN)$ 的复杂度，（极端情况的概率极低）
- 快速排序实际上是二叉搜索树排序：中序遍历BST。同理，两者的平均复杂度均为 $O(NlogN)$
- 快速排序比归并排序的表现更好
避免最糟情况( $O(N^2)$ $O (N^{2})$ )的方法:
- 使用随机性的方法，随机取到极端值的情况概率小
- 改变选取基准值的策略：先遍历数组，在选取恰当的基准值（中位数）
- 事先检查数组，如果快速排序很慢的情况再切换排序方法

$\begin{equation} NlogN \in \Omega(log(N!)) \end{equation}$

$log(N!)=log(N)+log(N-1)+log(N-2)+...+log(1) \le NlogN$

\begin{equation}log(N!) \in \Omega(N logN)\end{equation}$$$$log(\frac{N}{2})^{\frac{N}{2}}=\frac{N}{2}(logN-log2) \in \Theta (NlogN)\le log(N!)

对于任意一个 $N$ 个数字组成的排列，一共有 $N!$ 种情况，而每次比较需要比较两个数，得到两种不同的结果，这意味着对应的决策树每个节点最多有两个子节点，于是对应的决策树一共有 $log_2(N!)$ 层，所以排序至少要经历 $log_2(N!)$ 次才能得出答案，故任何比较算法的渐进下界为 $log(N!)=\Theta(NlogN)$