排序

void quickSort(vector<int> &a, int L, int R) {
    if (L == R) return;
    int i = L - 1, j = R + 1;
    int k = a[L + R >> 1];
    while (i < j) {
        do i++; while (a[i] < k);
        do j--; while (a[j] > k);
        if (i < j) swap(a[i], a[j]);
    }
    quickSort(a, L, j);
    quickSort(a, j + 1, R);
}

int cnt = 0;
void mergeSort(vector<int> &a, int L, int R) {
    if (L == R) return;
    vector<int> b(R - L + 1);
    int mid = L + R >> 1;
    mergeSort(a, L, mid);
    mergeSort(a, mid + 1, R);
    int i = L, j = mid + 1, k = 0;
    while (i <= mid && j <= R) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
            cnt += mid - i + 1;
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= R) {
        b[k++] = a[j++];
        cnt += mid - i + 1;
    }
    for (int i = L ; i <= R ; i++) a[i] = b[i - L];
}

void insertSort(vector<int> &a, int L, int R) {
    for (int i = L + 1 ; i <= R ; ++i) {
        int v = a[i];
        int j = i - 1;
        while (j >= L && v < a[j]) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = v;
    }
}

void bubbleSort(vector<int> &a, int L, int R) {
    for (int i = L ; i <= R ; i++) {
        for (int j = R ; j > i ; j--) {
            if (a[j - 1] > a[j]) {
                swap(a[j - 1], a[j]);
            }
        }
    }
}

void selectSort(vector<int> &a, int L, int R) {
    for (int i = L ; i < R ; i++) {
        int t = i;
        for (int j = i ; j <= R ; j++) {
            if (a[j] < a[t]) {
                t = j;
            }
        }
        swap(a[t], a[i]);
    }
}

void insertSort(vector<int> &a, int L, int R, int g) {
    for (int i = L + g ; i <= R ; ++i) {
        int v = a[i];
        int j = i - g;
        while (j >= L && v < a[j]) {
            a[j + g] = a[j];
            j -= g;
        }
        a[j + g] = v;
    }
}
void shellSort(vector<int> &a, int L, int R) {
    vector<int> g;
    for (int h = 1 ; h <= R ; h = 3 * h + 1 ) g.emplace_back(h);
    reverse(begin(g), end(g));
    for (auto &i : g) insertSort(a, L, R, i);
}