排序算法

选择排序

每次找到最小，与第一个元素交换位置。
大约需要N²/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]);
    }
}

插入排序

左边是有序的，每个元素往前面查找位置。
平均情况：~ N²/4次比较和~ N²/4次交换。平均情况下，每个元素向后移动半个数组位置。
最坏情况：~ N²/2次比较和~ N²/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成正比
缺点：非常脆弱。如果每次取最左边，反而是有序的时候需要~ N²/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次比较和恒定的额外空间。当空间十分紧张时（例如在嵌入式系统或者低成本的移动设备中）它很流行，因为它只用几行就能实现比较好的性能。
缺点：现代系统的很多应用很少使用它，因为无法利用缓存，因为很少和相邻的其他元素进行比较。