排序算法有多种，总是容易混淆，在此总结一下。
Input: sequence of <a1 a2 … an>
Output: premutation of <a1a2 …an`>
- 插入排序(Insertion Sort)
基本思想：逐个遍历数组中的每一个位置i，保证位置i之前的序列是sorted。原地排序。
伪代码：
InsertionSort(A[])
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
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9
插入排序的时间复杂度取决于输入的规模和有序程度，规模越大、越无序，花费时间越长。这是一种原地排序，时间复杂度为o（n2）
- 合并排序（Merge Sort）
基本思想：基于分治思想。减小要解决问题的规模，递归地合并数组。归并排序非原地排序，用空间换时间，来降低时间复杂度。
伪代码：
MergeSort(A[])
if n =1 ,done
Recursively sort A[1,…n/2] and A[n/2+1,…n]
Merge 2 sorted lists
Merge 步骤的复杂度o(n),T(n) = 2T(n/2)+n，故归并排序的时间复杂度为o(nlgn),在大规模输入情况下，归并排序由于插入排序。
- 快速排序（QuikSort）
基本思想：分治思想+原地排序。递归地划分数组。
伪代码：
QuickSort(A,p,q)
Partition (A,p,q)
x <- A[p]
i <- p
for j <- p+1 to q
do if A[j]<x
then i <- i+1
echange A[i] <-> A[j]
echange A[p] <-> A[i]
return
QuickSort(A,p,r-1);
QuickSort(A,r+1,p);
Partition的复杂度为O(n)
快排的最坏情况出现在数组已经排序好或者逆序排列，复杂度为O(n2),最好情况出现在总是选出的key值总能很好划分数组，复杂度为O(nlgn).优化的方法是随机选取key值，这样数组的输入就不在matter了。
- 堆排序（Heapsort）
基本思想：用大根堆的特性来排列数组中的元素。时间复杂度为O(nlgn),非原地排序。
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
