学习笔记——算法导论（2）

视频其实已经看到挺后面了，有非常非常冗长的不想看的数学证明。目前感觉还是以算法为主，数学推导过程除非比较基础的，用的比较多的，其他只看一看就好了。因为主要学习的目标还是学习算法，指导写程序，不进行太多的基础算法工作和应用。

快排(Quicksort)

分治法：

Divide： 将整个数组依据一个主元 x 分为两部分，一部分全部小于x，另一部分全部大于x。

Conquer: 对两个子数组再进行分割区分。

Combine: 已经排好了。

最坏情况： 输入数组为已经排序好的或者逆序排序好的数组 O(n^2)

其他几种情况下，时间均为 O(nlgn)

随机化快排：根据运行时间特点，将输入数组或者主元随机选取，这样就可以保证算法的时间不受输入情况的影响。不需要对输入数据进行任何假设（时间与输入数据完全无关）

排序最少消耗时间

比较模型下，可以使用决策树来对所有排序算法进行建模。因为总共排序可能结果共有 n! 种可能性，所以树的叶节点个数至少为 n! ，对于一个二叉树来说，n! 个叶节点的最小高度为 nlgn 。所以其最快运行时间为 O(nlgn)（在比较模型的前提下）。并且可以知道，堆排序和归并排序是渐进最佳的。

其中比较模型是指基于只能进行两个元素的互相比较得到某个元素较大的情况下的排序。

特殊情况下的线性时间排序算法

计数排序

输入数组取自有限的一个数组A， 这种情况下，建立一个A大小的数组，其中存储每一个数字出现的次数，然后重新将其写出来。

总时间 O(n+k) —- 不是比较排序

稳定排序

如果排序过程中，数字之间的相对位置保持稳定，不会出现交换，那么这个排序是稳定排序

基数排序

从最低位向最高位一位位排序，使用稳定排序方法。分配式排序。在排序其中每一位时，因为数量有限，可以使用计数排序。

桶排序

桶排序将一串有限的数字序列划分为M个子区间，然后将所有数字分配到各个桶中，再对每一个桶进行排序，最后依次输出所有桶中的数字，最终得到的内容即为一个有序序列。

分的桶越多，每一个桶中的元素数量越小，排序效率越高。但是空间代价也越高。

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

“桶”的大小的选择 T(n,b) = O(b/r*(n+2^r))

使 r = lgn。则 T = O(bn/lgn)

顺序统计

在n个元素中寻找第i小的数（特殊情况：中位数）

朴素方法：先对元素进行排序（O(nlgn)），然后取第i个数（O(1)）

使用快排的方法：

其中 RAND-PARTITION 和快排中的步骤一样。这样其实减少了一半的比较次数，比排序的方法快。但是最坏情况依然是快排的最坏情况（O(n^2)）。