iyidgnaw
5/12/2018 - 1:46 AM
Sort.md
Basic
Shell Sort
证明如果以2，3，4，6，8...这个这样的序列进行shell sort，那么算法复杂度是n(logn)^2.
当我们进行步幅为2的shell排序时，我们已经完成了步幅为4的shell排序，例如以下序列：
p,q,x,y,z
当我们比较z和x时，我们已知z>p,并且在本轮的2shell排序的前期我们已经实现了p和x的排序，所以我们一定可以保证此时处于x位置的元素一定大于位置p的元素。那么本轮的2shell排序在z这个位置我们实际上只需要和x一个元素进行比较，也就是说我们只需要和z-2位置的元素进行比较，也就是以O(1)的复杂度完成了这次局部排序，因此本轮2shell排序的总耗时就是o(n)。由此我们可以扩展到每一轮排序，因为对于每一轮h shell排序，我们已经完成了2h排序，因此每一轮的耗时就是线性的。由此对于整个算法的时间分析就变成了，我们需要多少轮这样的shell排序。
首先我们要知道每个大于2的整数都可以表示为2x+3y的形式，因此我们可以看到
O(nlogn)
Merge Sort
使序列局部有序是为了保证在合并两个子序列的时候可以用O(n)实现。
只有当子序列是局部有序的，我们才能不用每次提取出一个元素和另一个队列的所有元素进行比较。
由此就能够保证每次的合并的操作都是线性的。
对于mergesort的时间复杂度分析，我们可以采用master元素分析法。
首先写出时间复杂度：
T(n) =2* T(n/2) + cn
由此我们可以看出其符合master theorm case2 此时a=2,b=2,k=0,所以结果为c=1k=1，O(nlogn)
Quick Sort
- 如果采用一个pointer指向小于pivot的边界，那就无法保证数组在partition之后仍然有序。反之如果采用两个pointer分别从小于一侧以及大于一侧逼近，就可以保证数组最终的相对顺序仍然不变，此处的顺序是指，在所有大于pivot和小于pivot的两个split中的相对顺序没有改变。
-