排序总的问题就是:
输入一个序列 A[1···n]
要求输求它的递增排序之后的排列。
插入排序 (Insertion sort)
Pseudocode1
2for j = 2:n
insert key A[j] into the already sorted sub array A[1 ... j-1] by pairwise key-swaps down to its right position.
Complexity: $\theta(n^2)$
because at the worst case, it needs $\theta(n^2)$ compares and $\theta(n^2)$ swaps.
Binary Insertion sort
注意到在一般的插入排序中,我们会得到一个已经排好序的子序列,那么这时其实就可以用二分查找法来替代之前的逐个compare,这样能减少compare的次数。
Pseudocode1
2
3for j = 2:n
insert key A[j] into the already sorted sub array A[1 ... j-1]
Use binary search to find the right position
二分查找法花费 $\theta(log n)$ 时间,插入之后移动元素花费 $\theta(n)$ 时间。
Complexity:
$\theta(nlog n)$ comparisons, $\theta(n^2)$ swaps
归并排序 (Merge Sort)
采用的是 divide and conquer 的思想。
Pseudocode1
2
3If n = 1, done (nothing to sort)
Otherwise, recursively sort A[1 ... n/2] and A[n/2+1 ... n]
"Merge" the two sorted sub-arrays
Complexity:
$\theta(n)$ to merge a total of n elements(linear time)
$T(n) = 2T(n/2) + \theta(n)$
After plotting the recursion tree, we can find that there are 1+lgn
layers, and n
leaves in the tree. And for each layer, it totally costs cn
time. Therefore, complexity is $\theta(nlg n)$
可以看到,在这个树里面,每一层的complexity都是均等的
Solving Recurrences
对于不同的recurrence tree来说,每一层不同的cost决定了它的complexity主要集中在哪里。
如上面的归并排序是每一层都占相等的复杂度。
下面是两个例子:
叶子部分的计算占主要复杂度:
根部分的计算占主要复杂度: