选择排序
每次找到最小，与第一个元素交换位置。
大约需要N2/2次比较和N次交换，运行时间和输入无关，数据移动是最少的。
void selection_sort(int a[], int n)
{
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
swap(a[min], a[i]);
}
}
插入排序
左边是有序的，每个元素往前面查找位置。
平均情况：~ N2/4次比较和~ N2/4次交换。平均情况下，每个元素向后移动半个数组位置。
最坏情况：~ N2/2次比较和~ N2/2次交换。每个元素都要移动到最前面（倒序？）
最好情况：N-1次比较和0次交换。本来就是有序的。
void insert_sort(int a[], int n)
{
for (int i = 1; i < n; i++)
for (int j = i; j > 0; j--)
if (a[j] < a[j-1])
swap(a[j], a[j - 1]);
else break;
}
希尔排序
基于插入排序，使得任意相隔为h的元素都是有序的。代码量小，不需要额外的空间，如果们需要解决一个排序问题而又没有系统函数可用，可以先用希尔排序，再考虑是否值得替换为更加复杂的排序算法。
归并排序
优点：保证任意长度为N的数组排序所需时间与NlgN成正比
缺点：所需的额外空间和N成正比
void merge(int a[], int aux[], int lo, int mid, int hi)
{
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)
{
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
void merge_sort(int a[], int aux[], int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
merge_sort(a, aux, lo, mid);
merge_sort(a, aux, mid+1, hi);
if(a[mid + 1] > a[mid]) return;
merge(a, aux, lo, mid, hi);
}
快速排序
优点：实现简单，适用于各种不同的输入数据，且在一般应用中比其他排序算法要快得多。它是原地排序，所需时间和NlgN成正比
缺点：非常脆弱。如果每次取最左边，反而是有序的时候需要~ N2/2次比较。
可求第k大问题
int partition(int a[], int lo, int hi)
{
int i = lo, j = hi + 1;
while(true)
{
while (a[++i] < a[lo])
if (i == hi) break;
while (a[lo] < a[--j])
if (j == lo) break;
if (i >= j) break;
swap(a[i], a[j]);
}
swap(a[lo], a[j]);
return j;
}
void quick_sort(int a[], int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi);
quick_sort(a, lo, j-1);
quick_sort(a, j+1, hi);
}
堆排序
用数组表示，不用第一个0
k的结点的父结点的 k/2向下取整 ，子结点是2k和2k+1
一棵大小为N的完全二叉树的高度为 lgN向下取整
优点：唯一能够同时最有地利用空间和时间的方法，在最坏的情况下也能保证使用~2NlgN次比较和恒定的额外空间。当空间十分紧张时（例如在嵌入式系统或者低成本的移动设备中）它很流行，因为它只用几行就能实现比较好的性能。
缺点：现代系统的很多应用很少使用它，因为无法利用缓存，因为很少和相邻的其他元素进行比较。
