# 基于比较的排序

## 插入排序

- 时间复杂度：平均/最坏 $O(n^2)$
- 稳定
- 空间复杂度： $O(1)$ ，原址

## 选择排序

每次选出未排序序列中的最小的一个元素，放到已排序序列的末尾。

- 时间复杂度：平均/最坏 $O(n^2)$
- 不稳定
- 空间复杂度： $O(1)$ ，原址

## 冒泡排序

每次比较相邻的两个元素，如果顺序不对，就交换。

- 时间复杂度：平均/最坏 $O(n^2)$
- 稳定
- 空间复杂度： $O(1)$ ，原址

## 希尔排序

先将整个待排序的序列按步长分割成若干子序列分别进行直接插入排序，待整个序列基本有序时，再对全体进行一次直接插入排序。

- 时间复杂度下界 $\Omega(n(\frac{\lg n}{\lg\lg n})^2)$

## 堆排序

堆-接近完全二叉树

最大堆，维护代价 $O(\lg n)$

$n$个节点的堆，下标从 $1$ 到 $n$，叶节点为 $\lfloor n/2\rfloor + 1$ 到 $n$，需要证明这些是叶节点且其余不是叶节点

建堆，基于维护堆的函数，从 $\lfloor n/2\rfloor$ 到 $1$，依次调用维护堆的函数，可以显然看出其复杂度不超过 $O(n\lg n)$

堆排序，每次将堆顶的元素与最后一个元素交换，然后将堆的大小减一，再调用维护堆的函数，直到堆的大小为 $1$

分析时间复杂度有堆排序的总时间复杂度为 $\Theta(n\lg n)$，不过其常数较大

不稳定

空间复杂度 $O(1)$，原址

### 下面分析建堆的时间复杂度

只有堆顶的维护堆函数时间复杂度为 $O(\lg n)$，其余节点的高度都小于 $\lg n$

堆里有 $\lfloor \frac{n}{2}\rfloor$ 个非叶节点

堆高为 $h = \lfloor \lg n\rfloor$

可用数学归纳法证明高度为 $h$ 的节点个数为 $\lceil\frac{n}{2^{h+1}}\rceil$

因此总时间复杂度为

$$\sum_{h=0}^{\lfloor \lg n\rfloor}\lceil\frac{n}{2^{h+1}}\rceil\cdot O(h)=O(n\sum_{h=0}^{\lfloor \lg n\rfloor}\frac{h}{2^h})=O(n\sum_{h=0}^\infty\frac{h}{2^h})=O(2n)=O(n)$$

### 堆的应用

优先队列

## 快速排序

**任意**选取一个元素，将小于它的放在左边，大于它的放在右边，再对左右两边递归调用快速排序。

时间复杂度为 $T(n)=T(L)+T(R)+\Theta(n)$

最坏情况下，每次都划分为 $n-1$ 和 $0$ 两个子序列，时间复杂度为

$$T(n)=T(n-1)+T(0)+\Theta(n)=T(n-1)+\Theta(n)=\Theta(n^2)$$

最好情况下，每次都划分为 $\lfloor n/2\rfloor$ 和 $\lceil n/2\rceil$ 两个子序列，时间复杂度为

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)$$

### 随机化快速排序

每次随机选取一个元素，再进行划分，期望时间复杂度为 $\Theta(n\lg n)$

### 快速排序的分析

将数组 $A$ 的元素重新命名为 $z_1,z_2,\ldots,z_n$，定义随机变量 $X_{ij}=I\{z_i与z_j进行了一次比较\}$，其中 $I\{\cdot\}$ 为示性函数。定义 $Z_{ij}=\{z_i,z_{i+1},\ldots,z_j\}$

所以总的比较次数为

$$X=\sum_{i=1}^{n-1}\sum_{j=i+1}^nX_{ij}$$

其期望为

$$EX=\sum_{i=1}^{n-1}\sum_{j=i+1}^nEX_{ij}=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\frac{2}{j-i+1}<\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$

快速排序的最好和平均时间复杂度为 $O(n\lg n)$，最坏时间复杂度为 $O(n^2)$

空间复杂度平均为 $O(\lg n)$，最坏为 $O(n)$

不稳定，但可以有稳定的版本