最好时间复杂度为每次都正好找到最中间的一个数时时间复杂度为O（nlogn）。证明略。
最坏时间复杂度为每次都正好找到最旁边的数时时间复杂度为O(n^2)。证明略。
平均时间复杂度为O（nlogn），推导式如下：

快速排序每一步中，将元素分为左右两边需要遍历整个列表，耗时T(n)。假设最后定位的元素为最终第i个元素，则两个子问题复杂度分别为T(i)和T(n-i-1)。

则有：
$\begin{aligned} T(n) &= n + \frac{\sum_{i=0}^{n-1}{T(i)+T(n-i-1)}}{n} \\ &=n + \frac{2}{n}\times\sum_{i=0}^{n-1}{T(i)} \\ \end{aligned}$
令 $\sum_{i=0}^{n}T(i) = Sum(n)$ ，即有：
$\begin{aligned} T(n) &= n + \frac{2}{n} \times Sum(n-1) \\ Sum(n) &= \frac{n+1}{2}T(n+1) - \frac{n+1}{2}(n+1) \end{aligned}$
错位相减：
$\begin{aligned} Sum(n) - Sum(n-1) &= \frac{n+1}{2}T(n+1) - \frac{n+1}{2}(n+1) - \frac{n}{2}T(n) + \frac{n}{2}(n) \\ T(n) &= \frac{n+1}{2}T(n+1) - \frac{n}{2}T(n) - \frac{2n+1}{2} \\ \frac{T(n+1)}{n+2} &= \frac{T(n)}{n+1}+\frac{2n+1}{(n+1)(n+2)} \\ &= \frac{T(n)}{n+1}+\frac{1}{n}+\frac{1}{n+1} \\ &=... \\ &= \frac{T(1)}{2}+1+2\times(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})+\frac{1}{n+1} \\ \\ \frac{T(n)}{n+1}&=\frac{T(1)}{2}+1+2\times(\frac{1}{2}+...+\frac{1}{n-1})+\frac{1}{n} \\ &= O(1)+O(1)+O(logn)+O(\frac{1}{n}) \\ &= O(logn) \end{aligned}$
其中由于 $\frac{1}{x}=\frac{d(logx)}{dx}$ ，因此 $\frac{1}{2}+...+\frac{1}{n-1}=O(logn)$ 。

则有：
$\begin{aligned} T(n)&=(n+1)\times O(logn)\\ &=O(n)\times O(logn)\\ &=O(nlogn) \end{aligned}$

额外空间复杂度

考虑栈深度，额外空间复杂度为O（logn）。由于快速排序主要步骤在于分，因此必须自上而下的进行递归，无法避免栈深度。

原地排序

虽然快速排序有额外空间复杂度，但并不妨碍它是一个原地排序。

不稳定

堆排序在分操作时将元素左右交换，会破坏稳定性。

链表形式特点

时间复杂度不变
空间复杂度不变
变为稳定排序※

手写时的易错点

分成左右子序列时最好完全分开（一边用<=一边用>），不然容易造成死循环。
分左右子序列时仔细考虑最初下标位置与最终下标位置，以及对应位置的值的大小。
不要忘记递归的结束条件。

归并排序

思想

分治法：先把两个子序列各自排好序，然后再合并两个子序列。即：简单分割，复杂合并。主要步骤在于合并。

要点

时间复杂度推导式：T(n) = 2T(n/2) + T(合)
平均、最好、最坏时间复杂度都是O（nlogn），推导过程略。
额外空间复杂度为O（n），合并时必须准备额外空间。但由于主要步骤在于合并，可以自下而上地进行迭代合并，可以不使用栈。
非原地排序
稳定排序

链表形式

时间复杂度不变
额外空间复杂度变为O(1)※
稳定排序
只能使用迭代形式，不能使用递归形式

易错点

合并时一边结束时另一边还未结束，需要把那一边也放入合并后序列中
保持稳定排序：合并时左序列等于右序列时也采用左序列
不要忘记递归结束条件
不要忘记循环递进条件

进阶

原地归并排序：时间复杂度为O（log^2n），牺牲合并的时间复杂度进行原地排序。
多路归并排序：使用竞标树，多路归并，用于磁盘IO。

插入排序

思想

有序序列不断扩张，每次从无序序列中取出元素加入有序序列，直至长度为N则完成排序。

每次将无序序列当前元素插入有序序列，复杂度取决于有序序列。

要点

最坏、平均时间复杂度：O（n2）
最好时间复杂度：基本有序情况下，O（n）
额外空间复杂度：O（1）
原地排序
稳定排序
每次插入时都要移动序列，写次数较多
若查找插入位置时使用二分法查找，则可加快时间。（但不足以对时间复杂度造成影响，且最好时间复杂度也会上升为O(nlogn)）

链表形式

最好，最坏，平均时间复杂度不变
额外空间复杂度不变
稳定排序
插入时不再需要移动序列，但也不能使用二分法查找

进阶——希尔排序

要点：

插入排序的优点在于当序列基本有序时，时间复杂度可逼近为O(n)。

但插入时移动有序序列中元素所耗时间较多，而每次只移动一步。但实际上当序列分布均匀时，有序序列中排靠后的元素在整个序列中也会排靠后。

可以把序列分为几个大步长序列，在最初的几次插入放开移动步长，让大的元素直接移动到较后位置。再往后慢慢缩小步长，此时序列基本有序，可以利用基本有序时插入排序的优势。
时间复杂度
1. 当步长为2^i时，不能使时间复杂度缩短为O(nlogn)。因为一个子序列所有元素有可能比另一个子序列最大元素都要大，这时插入排序仍需进行约n^2次操作
2. 当步长为2^i时效率较低，因为当步长为4已经有序时，步长为2再比较是无用比较。但由于1.的问题，不能节省比较时间。
3. 当步长之间最小公约数较少，甚至互质时，无用比较次数会降低。
4. 最坏时间复杂度下限为 $O(nlog^2n)$ （当步长采用 $2^i3^j$ 时），但一般希尔排序平均时间复杂度都为 $O(n^{\frac{3}{2}})$
额外空间复杂度O(1)
原地排序
不稳定排序：希尔排序步长较大时会发生前后跳转。
不能写为链表形式

选择排序

思想

有序序列不断扩张，每次从无序序列中取出元素加入有序序列，直至长度为N则完成排序。

每次将选无序序列中最小元素加到有序序列末尾，复杂度取决于无序序列。

要点

最坏、平均时间复杂度：O（n2）
最好时间复杂度：O（n2），如能保证无序部分的最小元素所在位置一定（堆排序），能降低时间复杂度
额外空间复杂度：O（1）
原地排序
不稳定排序（采用元素交换策略时）
每次找到最小元素后，只需交换一次位置即可，写次数较少。
若找到最小元素后，不直接交换而是进行数组移动，则可进行稳定排序，但写次数变多，与插入排序相比没有优势，也不能使用二分查找进行简化。

链表形式

最好，最坏，平均时间复杂度不变
额外空间复杂度不变
变为稳定排序※（因为链表不需要数组移动，稳定排序方式的缺点得以消除）

进阶——堆排序

要点：

选择排序中耗时最多的是取出无序序列中最小值的时间，需要遍历整个无序序列。

但实际上我们只关心无序序列中的最小值，而不关心其他值的位置。通过将无序序列建为堆，减少选择时间，降低总的时间复杂度。
时间复杂度O（nlogn）
额外空间复杂度O（1）
原地排序
不稳定排序
操作时间复杂度：每次向下比较关注一个节点与其左右子堆顶元素，每次向上比较只关注节点与其父元素（大顶堆，堆大小为n）
- 下沉：向下比较，若顶元素不是最大，将顶元素与较大的子堆堆顶元素交换。递归处理该子堆顶元素，直到向下比较顶元素最大。
  
  最好时间复杂度O（1），最坏时间复杂度为O（h）=O（logn），平均O（logn）
- 上浮：向上比较，若元素比其上层要大，交换该元素与其上层元素。递归处理其上层元素，直到向上比较不比上层要大。
  
  最好时间复杂度O（1），最坏时间复杂度O（h）=O（logn），平均O（logn）
- 入堆：堆扩容一位，将新元素插到尾部，将该元素上浮，最坏、平均时间复杂度O（logn）
- 出堆：取出堆顶元素，将尾部放到堆顶，将该元素下沉，最坏、平均时间复杂度O（logn）
- 缺点：通常堆尾元素较小，出堆时将堆尾元素放到堆顶再下沉基本要沉到堆底，无用比较较多
建堆时间复杂度O（n）
- 策略1：从头开始建堆，逐个元素插入，时间复杂度取决于最后一层，时间复杂度为O（nlogn）
  - 每次将堆扩容一位，将末尾元素上浮。
  - 时间复杂度推导：
    
    每次插入时间：
    $\begin{aligned} T(i) &= h\\ &= logi \end{aligned}$
    则有总时间：
    $\begin{aligned} T(n) &= \sum_{i=0}^{n}logi\\ &= 1\times1 + 2\times2+ 3\times4 + ...+h\times \frac{n}{2} \\ \\ 2T(n) &= 1\times2 + 2\times4+ 3\times8 + ...+h\times n \\ \\ 2T(n)-T(n) &= h\times n - (1+2+4+...+2^{h-1}) \\ &= h\times n - O(2^h) \\ \\ T(n) &= nlogn - O(2^h) \\ &= O(nlogn) \end{aligned}$
    即时间复杂度为 $O(nlogn)$
- 策略2：从后开始建堆，小堆合并（逐个元素下沉），时间复杂度为O（n）
  - 每次堆合并时，有三部分：左子堆，右子堆，顶元素。下沉顶元素。
  - 时间复杂度推导：
    
    第i个元素合并时，时间为：
    $\begin{aligned} T(i) &= h_{子堆} \end{aligned}$
    则有总时间：
    $\begin{aligned} T(n) &= \sum_{i=0}^{n} (h_{子堆}) \\ &= h + (h-1)\times2 + ... + 2 \times \frac{n}{4} + 1 \times\frac{n}{2}\\ \\ 2T(n) &= h \times 2 + (h-1) \times 4 + ... + 2 \times \frac{n}{2} + n \\ \\ 2T(n) - T(n) &= n + \frac{n}{2} + ... + 2 - h \\ \\ T(n) &= O(n) - h \\ &= O(n) \end{aligned}$
    即时间复杂度为 $O(n)$
  - 虽说每步是做一个小堆合并，但实际上从堆尾到堆头遍历，相当于仅关注元素没有稳定，相当于可以直接使用下沉操作。

基于比较的排序算法时间复杂度下限：逆序对思想

基于比较的排序算法可以看作序列逆序对的消除。完全随机序列逆序对数量为O(n^2)，若一次元操作只消除一个逆序对，则时间复杂度不会低于O(n^2)。降低时间复杂度关键在于一次消除多个逆序对。

希尔排序通过增大最初的步长来企图一次消除多个逆序对。
归并排序消除逆序对最主要在于归并步骤。最后几次合并每个子步骤用O(1)时间消除O(n)个逆序对。
快速排序消除逆序对最主要在于划分步骤。每个划分步骤用O(n)时间消除O(n)+O(左长度×右长度)个逆序对。
堆排序逆序对消除方式比较Tricky，但可以看出消除逆序对大致在于出堆步骤，通过O(logn)时间复杂度消除O(n)个逆序对。（左小右大排序时需要建立左大右小的大顶堆，建堆时基本没有消除逆序对）

最后

这篇文章我们主要关注了排序算法中的大头——基于比较的排序算法。在下篇文章，我们再来看一下不基于比较的排序算法，以及外排序与并行排序。