選擇排序

每次找到最小，與第一個(gè)元素交換位置。
大約需要N²/2次比較和N次交換，運(yùn)行時(shí)間和輸入無關(guān)，數(shù)據(jù)移動(dòng)是最少的。

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]);
    }
}

插入排序

左邊是有序的，每個(gè)元素往前面查找位置。
平均情況：~ N²/4次比較和~ N²/4次交換。平均情況下，每個(gè)元素向后移動(dòng)半個(gè)數(shù)組位置。
最壞情況：~ N²/2次比較和~ N²/2次交換。每個(gè)元素都要移動(dòng)到最前面（倒序？）
最好情況：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的元素都是有序的。代碼量小，不需要額外的空間，如果們需要解決一個(gè)排序問題而又沒有系統(tǒng)函數(shù)可用，可以先用希爾排序，再考慮是否值得替換為更加復(fù)雜的排序算法。

歸并排序

優(yōu)點(diǎn)：保證任意長(zhǎng)度為N的數(shù)組排序所需時(shí)間與NlgN成正比
缺點(diǎn)：所需的額外空間和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);
}

快速排序

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，適用于各種不同的輸入數(shù)據(jù)，且在一般應(yīng)用中比其他排序算法要快得多。它是原地排序，所需時(shí)間和NlgN成正比
缺點(diǎn)：非常脆弱。如果每次取最左邊，反而是有序的時(shí)候需要~ 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);
}

堆排序

用數(shù)組表示，不用第一個(gè)0
k的結(jié)點(diǎn)的父結(jié)點(diǎn)的 k/2向下取整 ，子結(jié)點(diǎn)是2k和2k+1
一棵大小為N的完全二叉樹的高度為 lgN向下取整
優(yōu)點(diǎn)：唯一能夠同時(shí)最有地利用空間和時(shí)間的方法，在最壞的情況下也能保證使用~2NlgN次比較和恒定的額外空間。當(dāng)空間十分緊張時(shí)（例如在嵌入式系統(tǒng)或者低成本的移動(dòng)設(shè)備中）它很流行，因?yàn)樗挥脦仔芯湍軐?shí)現(xiàn)比較好的性能。
缺點(diǎn)：現(xiàn)代系統(tǒng)的很多應(yīng)用很少使用它，因?yàn)闊o法利用緩存，因?yàn)楹苌俸拖噜彽钠渌剡M(jìn)行比較。