排序

归并排序：

void merge(vector<int>& a, int low, int mid, int high, vector<int>& aux){
    int i = low, j = mid+1;
    for(int k = low; k <= high; ++k){
        aux[k] = a[k];
    }
    for (int k = low; k <= high; ++k) {
        if (i > mid) a[k] = aux[j++];
        else if (j > high) a[k] = aux[i++];
        else if (aux[j] < aux[i]) a[k] = aux[j++];
        else a[k] = aux[i++];
    }
}
void mergesort(vector<int>& a) {
    int n = a.size();
    vector<int> aux(n, 0);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n-i; j +=i+i) {
            merge(a, j, i+j-1, min(i+i+j-1, n-1), aux);
        }
    }
    return;
}

快速排序：

void swap(vector<int>& a, int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
    return;
}

int partition(vector<int> a, int lo, int hi) {
    int i = lo, j = hi + 1;
    int value = a[lo];
    while (i < j){
        while (a[++i] < value) if (i == hi) break;
        while (a[--j] > value) if (j == lo) break;
        swap(a, i, j);
    }
    swap(a, lo, j);
    return j;
}

void sort(vector<int>& a, int beg, int end){
    if (beg <= end) return;
    int j = partition(a, beg, end);
    sort(a, beg, j-1);
    sort(a, j, end);
}

void quicksort(vector<int>& a){
    sort(a, 0, a.size()-1);
}

堆排序：

void sink(vector<int>& a, int k, int n){
    while(2*k <= n){
        int j = 2*k;
        if(j < n && a[j] < a[j+1]) j++;
        if (a[k] >= a[j]) retrun;
        swap(a, k, j);
        k = j;
    }
}

void heapsort(vector<int>& a){
    int n = a.size();
    for (int k = n/2; k >= 1; k--) {
        sink(a, k, n);  // 建堆
    }
    while (n>1){
        swap(a, 1, n--);
        sink(a, 1, n);
    }
}

希尔排序：

void shellsort(vector<int>& a){
    int n = a.size();
    int h = 1;
    while (h < n/3) h = 3*h + 1;
    while (h >= 1){
        for (int i = h; i < n; ++i){
            for (int j = i; j >= h && a[j] < a[j-h]; j -= h){
                swap(a, j, j-h);
            }
        }
        h /= 3;
    }
    return;
}