# 排序问题

输入一个序列$\scr{A}=\langle a_1,a_2,\ldots,a_n\rangle$，输出一个原序列$\scr{A}$的排列$\langle a_1',a_2',\ldots,a_n'\rangle$使得$a_1'\leq a_2'\leq\cdots\leq a_n'$

## 插入排序

```
for j <- 2 to n do
    key <- A[j]
    i <- j - 1
    while i > 0 and A[i] > key do
        A[i + 1] <- A[i]
        i <- i - 1
    A[i + 1] <- key
```

最好情况，每次$1$，总为$n$

最坏情况，每次$i$，总为$\frac{n(n-1)}{2}$

平均情况，每次$\frac{i}{2}$，总的为$\frac{n(n-1)}{4}$

> 注意此处的平均并不严谨，假设了输入空间是$n$个数的所有可能排列，这与每次比较中比较一半的数并不等同

平滑分析，一个原本复杂的问题在抖动时很大概率找到一个可以非常快解决的问题，那么原本的问题就可以认为是非常快解决的

## 归并排序

典型分治算法，递归

```
mergesort(A, p, r):
if p < r then
    mergesort(A, p, (p + r) / 2)
    mergesort(A, (p + r) / 2 + 1, r)
    merge(A, p, r)
```

假设总时间复杂度为$T(n)$，则有$T(n)=2T(n/2)+\Theta(n)$