排序是基础且重要的问题，排序算法有几十种，可以证明，有些算法是渐进最优的。那为什么还会存在一些不那么快的算法呢？快慢是从时间尺度来衡量的，空间呢？那些运行很快的排序算法，需要多大的空间呢？排序是不是稳定的呢？如果不是，转化为稳定的排序，又需要多少额外的时间和空间呢？
每种算法各有千秋，不存在任何方面都最优的算法，只有限定条件下的最优解，而这也正是我们努力想要求得的。
什么是排序：
输入：长度为n的序列输出：长度为n的非降序列为什么要进行排序：
产生有序的输为另一程序做一些前期准备（如二分查找）排序算法可分为基于比较的排序和线性时间排序（至少要遍历所有元素）。常见的基于比较排序的算法有：冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序等。任何一种基于比较的排序算法都可以用决策树模型来描述。
决策树每一个叶节点代表一种可能的排序结果，n个数字（没有重复）的全排列共有n!种情况，因此决策树叶节点数量大于等于n!，又因为简单决策树是二叉树，所以叶节点的数量小于等于 2h （h为树的高度）n! ≤ #leaves ≤ 2h ，由斯特林公式可得h ≥ n logn2 （斯特林公式是对阶乘的近似估计，渐进情况下可简记为：n! = nn ）。
结论： 所有基于比较的排序最坏情况下的下界为nlogn。
插入排序： 伪码：
for j = 2 to n key = A[j] i = j – 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i – 1 A[i+1] = key运行时间:
最坏情况：输入逆序 T(n)=∑j=2nθ(j)=θ(n2)归并排序：：
步骤：
Merge sort A[1,…,n]
If n = 1, doneRecursively sort A[1,…,⌈n/2⌉] and A[⌈n/2⌉+1,n]Merge 2 sorted lists关键：
归并： 在每一步中，只关注两个数组的首元素，挑选出更小的，然后把数组指针前移一位，每一步只需常数时间，与数组规模无关Time = θ(n)归并伪码：
Merge(lo, mi, hi) //A[lo, hi) mi = (lo + hi) / 2 l = mi - lo L = A[0, mi) Let L[0, m) be new array //开辟原数组一半的额外空间 for j to l -1 L[j] = A[j] for j = 0 to l or k = mi to hi if j < l and (hi <= k or L[j] <= A[k]) //L[j] <= A[k]中的"<="以及下一个if语句中的[k] < L[j]中的“<”保证了归并排序的稳定性 A[i++] = L[j++] if k < hi and (l <= j or A[k] < L[j]) A[i++] = A[k++]T(n) = θ(1) + 2T(n/2) +θ(n)
递归树： T(n) = 2T(n/2) + cn c > 0 用cn显式地替换掉了隐式的θ(n)
由递归树可得归并排序的运行时间： T(n)=θ(nlogn)
堆排序： 插入排序和归并排序的时间复杂度分别是 O(n2) 、 O(nlogn) ，显然归并排序更快，但是归并排序需要额外开辟空间，而插入排序是原址的（只需要常数个额外空间存储临时数据）。有没有集合这两种排序算法优点的算法呢？堆排序便是一种。
堆排序需要借助一种被称为“堆”的数据结构，堆不仅可以用于堆排序，还可以构造优先队列。
堆具有两种特性：
结构性：逻辑上，等同于完全二叉树； 物理上，直接借助数组实现堆序性：物理上，直接借助数组实现； 数值上，父节点大于等于子节点的值二叉堆的结构性，决定了它可以用数组隐性表示。任一节点其父节点和左右子节点，都可以由自身索引唯一、明确得到。以数组A[1,…,n]为例，A[i]父节点为A[i/2]，左子节点和右子节点分别为A[2i]和A[2i+1]（动手画一棵完全二叉树，仔细观察，不难发现此规律）。
堆排序的原理： 算法输入是数组A[1,…,n]。首先将数组排列成堆，A[1]为数组中的最大元素，交换A[1]和A[n]。然后考察数组A[1,…,n-1]，将数组重新排列成堆，交换A[1]和A[n-1]。接着考察A[1,…,n-2]，重复上述过程，直至排序完毕。总的来说，堆排序包括一次初始建堆过程，n-1次交换和重排成堆。
堆排序的关键:建堆 1. 自上而下的上滤法，对应着自左向右扫描数组 2. 自下而上的下滤法，对应着自右向左扫描数组
自上而下的上滤法：最坏情况下，需要上滤所有节点的深度和 只考虑叶节点：深度均为 O(logn) ，累计耗时 O(nlogn)
自下而上的下滤法：最坏情况下，需要下滤所有节点的高度和 记H(i)高度为i的完全二叉树所有节点的高度之和。将高度为i的树看作是两棵高度为i-1的树和一个高度为i的节点，于是有H(i) = 2H(i-1) + i; 仿照图2画出递归树，应用一个小技巧，从底层往上累加求和:
H(i)=1×2i−1+2×2i−2+2×2i−3+...+(i−1)×21+i×20=∑n=1in×2i−n=2i∑n=1in2n
Sn=∑n=1in2n=121+222+323+...+i−12i−1+i2i
Sn2=12Sn=122+223+324+...+i−12i+i2i+1
Sn2=Sn−Sn2=121+122+123+...+12i−1−i2i+1
Sn=2Sn2=120+121+122+...+12i−2−i2i=2−i+22i
H(i)=2iSn=2i+1−(i+2)
二叉堆的结构性，决定了它可以用数组隐性表示。任一节点其父节点和左右子节点，都可以由自身索引唯一、明确得到。以数组A[1,…,n]为例，A[i]父节点为A[i/2]，左子节点和右子节点分别为A[2i]和A[2i+1]。
满二叉堆的高度为h则节点数之和 n=2h+1−1
完全二叉堆叶节点的个数至少为n/2，简单证明如下： 当最底层只有两个叶节点时，完全二叉堆叶节点的数量最少: #leaves = 2h−1+1
该情形下所有节点之和： n=2h+1
leavesn=2h−1+12h+1>2h−12h=12⇒leaves>n2
快速排序：
步骤：
Divide: Partition array into 2 subarrays around pivot x such that elements in lower subarray ≤x ≤ elements in upper subarrayConquer: recursively sort 2 subarrays(lesser and greater)Combine: trivial关键：
partition： 在每一步中，即递归的分化数组：选定一个主元（pivot），将数组中所有比主元小的元素移动到主元的左侧，所有比主元大的元素移动到主元的右侧。
partition伪码：
Partition(A, p, q) //A[p,...q] x = A[p] //pivot = A[p] i = p j = p + 1 for j = p +1 to q if A[j] ≤x i = i + 1 exchange A[i] with A[j] exchange A[p] with A[i] returnpartition运行时间:
最坏情况（假定没有重复元素）：输入有序（顺序或逆序)，分化的一侧没有元素(等同于插入排序逆序输入) T(n)=T(0)+T(n−1)+θ(n)=θ(n2) 最好情况：将数组分化为相等的两个部分：n/2和n/2(最好情况的一种。关键不是二等分数组，而是分化两侧的数据 都与n有关，不是常量)T(n)=2T(n2)+θ(n)=θ(nlogn)
在快速排序最好情况和最坏情况之间，我第一次体会到了分治法的强大
在最坏情况下快排的时间复杂度是 O(n2) ，这是由于输入数组有序造成的，可以使用随机化快排，即随机挑选pivot，而不是直接选取数组首元素作为pivot，随机化快排的期望运行时间是[O(n\log n)]。
归并排序和快速排序，都运用了分治思想。却走了两条不同的路：快速排序把较多时间用在“分”上，递归的分化；归并排序把较多的时间用在了“治”上，递归的归并。虽然快速排序不能像归并排序具有最优下界，但是，在实际应用中快速排序往往更快。
PS： 数学之美番外篇：快排为什么那样快
