各大排序模板

快速排序

int a[N];//待排序数组
inline void swap(int& x, int& y) {
    int tmp = x;
    x = y;
    y = tmp;
}
void quick_sort(int l, int r) {
    if (l >= r)return;
    swap(a[l], a[(l + r) / 2]);
    int i = l, j = r, x = a[l];
    while (i < j) {
        while (i < j && a[j] >= x)j--;
        if (i < j)a[i++] = a[j];
        while (i < j && a[i] < x)i++;
        if (i < j)a[j--] = a[i];
    }
    a[i] = x;
    quick_sort(l, i - 1);
    quick_sort(i + 1, r);
}

选择排序

int a[N];//待排序数组
inline void swap(int& x, int& y) {
    int tmp = x;
    x = y;
    y = tmp;
}
void choose_sort(int l, int r) {
    for (int i = l; i < r; i++) {
        int k = i;
        for (int j = i + 1; j <= r; j++) {
            if (a[j] < a[k])k = j;
        }
        swap(a[i], a[k]);
    }
}

归并排序

int a[N];//待排序数组
int b[N];//merge时用的临时数组
void merge(int l, int r) {
    int mid = (l + r) >> 1;
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (j > r || i <= mid && a[i] < a[j])b[k] = a[i++];
        else b[k] = a[j++];
    }
    for (int k = l; k <= r; k++)a[k] = b[k];
}
void merge_sort(int l, int r) {
    if (l == r)return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r);
}