【资料图】

快速排序

#include using namespace std;const int N = 1e6 + 10;int n;int q[N];void position(int q[], int l, int r){        if (l >= r) return ;    //  边界        int x = q[l], i = l-1, j = r+1;        while(i < j) {            while (q[++i] < x); // 从左往右扫描            while (q[--j] > x); // 从右往左扫描            if(i < j) {                 int temp = q[i];                q[i] = q[j];                q[j] = temp;            }        }        position(q, l, j); // 对左区间排序        position(q, j + 1, r); // 对右区间排序}int main() {    scanf("%d", &n);        for(int i = 0; i < n; i++)        scanf("%d", &q[i]);    position(q, 0, n-1);    for(int i = 0; i < n; i++)        printf("%d ", q[i]);    return 0;}

归并排序

#include using namespace std;const int N = 1000001;int n, a[N], temp[N];void position(int a[], int l, int r){    if(l >= r) return ;    int mid = l + r >> 1;    //  递归    position(a, l, mid), position(a, mid+1, r);    int k = 0, i = l, j = mid+1;    // 归并    while(i <= mid && j <= r)        if(a[i] <= a[j])            temp[k++] = a[i++];        else            temp[k++] = a[j++];    //  收尾    while(i <= mid) temp[k++] = a[i++];    while(j <= r) temp[k++] = a[j++];        //  整合成一个有序序列    for(i = l, j = 0; i <= r; i++, j++)        a[i] = temp[j];}int main(){    cin >> n;    for(int i = 0; i < n; i++) {        scanf("%d", &a[i]);    }    position(a, 0, n-1);    for(int i = 0; i < n; i++) {        cout << a[i] << " ";    }    return 0;    }

解法：

  1. 区间[L, R] => [L, mid] 和 [mid + 1, R]
  2. 递归排序[L, mid] 和 [mid + 1, R]
  3. 归并，将左右两个有序序列合并成一个有序序列

归并排序----逆序对的数量

#include using namespace std;typedef long long LL;const int N = 100010;int n, q[N], temp[N];LL position(int l, int r){    if(l >= r) return 0;        int mid = l + r >> 1;    LL teg = position(l, mid) + position(mid+1, r);    int k = 0, i = l, j = mid+1;    while(i <= mid && j <= r){        if(q[i] <= q[j])            temp[k++] = q[i++];        else {            temp[k++] = q[j++];            teg += mid - i +1 ;        }                }    while(i <= mid)         temp[k++] = q[i++];    while(j <= r)         temp[k++] = q[j++];    for(i = l, j = 0; i <= r; i++, j++)        q[i] = temp[j];    return teg;}int main() {    cin >> n;    for(int i = 0; i < n; i++)        cin >> q[i];        cout << position(0, n-1) << " ";    return 0;}

思路：使用归并排序解题时，逆序对分为三种情况：全在左区间；全在右区间；一个在左区间一个在右区间。对于第三种情况，当左区间（已排序）的一个数i刚好大于右区间的一个数j，那么mid+1 >= i 的数都大于j，就可以得出teg = mid - i + 1.

推荐内容