「模板」各种排序板子

快速排序

void quick_sort(int *q, int l, int r) {
    if (l >= r)
        return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

sort

void sort(int *q, int l, int r);
//c++自带排序

归并排序

int ans[300005];
void merge_sort(int *a, int x, int y) {
    if (y - x > 1) {
        int mid = x + (y - x) / 2;
        int p = x, q = mid, i = x;
        merge_sort(a, x, mid);
        merge_sort(a, mid, y);
        while (p < mid || q < y) {
            if (q >= y || (p < mid && a[p] <= a[q]))
                ans[i++] = a[p++];
            else {
                ans[i++] = a[q++];
            }
        }
        for (int i = x; i < y; i++) a[i] = ans[i];
    }
}

冒泡排序

void bubble_sort(int *a, int l, int r) {
    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            if (a[i] > a[j])
                swap(a[i], a[j]);
        }
    }
}