排序算法专栏

快速排序

快速排序

快速排序的思想在于二分后进行递归，时间复杂度。
找到一个基准值pivot，把小于等于pivot的放在左半边，大于等于pivot的放在右半边。
然后递归排序两个子序列。

快排其实边界问题比较多，不是那么好写，建议找个自己最顺眼的模板，直接背模板。

#include <iostream>
using namespace std;
#define N 100010
int n;
int v[N];
void quick_sort(int s, int e) {
    if (s >= e) return;
    int left = s - 1, right = e + 1;
    int pivot = v[s + e >> 1];
    while (left < right) {
        while(v[++left] < pivot);
        while(v[--right] > pivot);
        if (left < right) {
            swap(v[left], v[right]);
        }
    }
    quick_sort(s, right);
    quick_sort(right + 1, e);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> v[i];
    }
    quick_sort(0, n - 1);
    for (int i = 0; i < n; i ++) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

第k大的数

寻找第k大的数也是基于快速排序的思想，时间复杂度O(n)。
第一步仍然是找到一个基准值pivot，把小于等于pivot的放在左半边，大于等于pivot的放在右半边。
之后我们根据两边数量和k的关系，只在一边进行搜索。

#include <iostream>
using namespace std;

#define N 100010
int n, k;
int v[N];

int quick_select(int s, int e, int k) {
    if (s == e) return v[s];
    int left = s - 1, right = e + 1;
    int pivot = v[left + right >> 1];
    while(left < right) {
        while(v[++ left] < pivot);
        while(v[-- right] > pivot);
        if (left < right) {
            swap(v[left], v[right]);
        }
    }

    int ln = right - s + 1;
    if (k <= ln) {
        return quick_select(s, right, k);
    } else {
        return quick_select(right + 1, e, k - ln);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++) {
        cin >> v[i];
    }

    cout << quick_select(0, n - 1, k) << endl;
    return 0;
}

归并排序

归并排序

归并排序的思想依旧是基于分治，首先把前后两部分数组排好序。
然后再通过双指针算法合并两个排好序的数组。时间复杂度。

#include <iostream>
using namespace std;

#define N 100010
int n;
int v[N], t[N];

void merge_sort(int s, int e) {
    if (s == e) return;
    int mid = s + e >> 1;
    merge_sort(s, mid);
    merge_sort(mid + 1, e);

    int left = s, right = mid + 1;
    int idx = s;
    while (left <= mid && right <= e) {
        if (v[left] < v[right]) {
            t[idx ++] = v[left ++];
        } else {
            t[idx ++] = v[right ++];
        }
    }

    while(left <= mid) {
        t[idx ++] = v[left ++];
    }

    while (right <= e) {
        t[idx ++] = v[right ++];
    }

    for (int i = s; i <= e; i ++) {
        v[i] = t[i];
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> v[i];
    }

    merge_sort(0, n - 1);

    for (int i = 0; i < n ; i ++) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

求逆序对的数量

我们通过归并排序来计算逆序对的数量。
根据归并排序的过程，我们可以把逆序对分为三类，两个数都在左半边，两个数都在右半边，两个数分别在两边。
左半边的逆序对和右半边的逆序对可以通过递归求解。
第三类的逆序对我们考虑归并的过程，如果左半边第一个数比右半边第一个数小，左半边第一个数先进行归并，由于这个数在左边，排完序后依旧在左半边，因此该过程不会产生逆序对数量的变化。如果右半边的第一个数比左半边第一个数小，右边第一个数先进行归并，归并完之后，这个数放在了前面，因此该过程会改变数的顺序，因此可以在此时计算逆序对。
由于右边的第一个数比左边第一个数小，因此，右边第一个数小于左边剩下的所有数，因此左边剩下的所有数都会和右边第一个数形成一个逆序对，所以当前的归并步骤产生逆序对的数量为左边剩下数的数量。
最终归并完成，返回总共逆序对的数量。

#include <iostream>
using namespace std;

#define N 100010
typedef long long LL; 
int d[N], t[N];
int n;

LL merge_sort(int s, int e) {
    if (s == e) return 0;
    int mid = s + e >> 1;
    LL ans = 0;
    ans += merge_sort(s, mid);
    ans += merge_sort(mid + 1, e);

    int p1 = s, p2 = mid + 1;
    int idx = s;
    while (p1 <= mid && p2 <= e) {
        if (d[p1] <= d[p2]) {
            t[idx ++] = d[p1 ++];
        } else {
            ans += mid - p1 + 1;
            t[idx ++] = d[p2 ++];
        }
    }

    while (p1 <= mid) {
        t[idx ++] = d[p1 ++];
    }

    while (p2 <= e) {
        t[idx ++] = d[p2 ++];
    }

    for (int i = s; i <= e; i ++) {
        d[i] = t[i];
    }

    return ans;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        cin >> d[i];
    }

    cout << merge_sort(0, n - 1) << endl;
    return 0;
}