Java教程

快速排序&归并排序&逆序对数量模板及分析

本文主要是介绍快速排序&归并排序&逆序对数量模板及分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序

思路

1. 确定分界点的值x

三种选择:取左边界q[l],取中间值q[(r + 1)/2],取右边界q[r]

2. 调整区间

把该序列分为两部分,使得所有小于等于x的在左边部分,大于等于x的在右边部分

实现方法1-略暴力

  1. 定义两个数组a,b
  2. 扫描数组q,把小于x的放入a数组,把大于等于x的放入b数组
  3. ab赋值给q

实现方法2-推荐

  1. 定义两个指针i, j分别指向q的左右两端

  2. i向左移动,直到遇到q[i] > x暂停

  3. 随后,j向右移动,直到遇到q[j] < x暂停

  4. 交换q[i]q[j]的值,然后i向左移动一次,j向右移动一次

  5. i < j时,重复2~4步

3. 递归处理

对左右两部分递归执行1,2两步

时间复杂度 Θ(nlogn)

期望上,快速排序平均分为logn层(因为分界值的选择不同而产生差异),每层的扫描交换复杂度之和是O(n)所以平均时间复杂度Θ(nlogn)

模板

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

练手

AcWing 785. 快速排序

AcWing 786. 第k个数

归并排序

思路

1. 确定分界点

使用数组的中间点为分界点,即mid = (left + right) / 2

2. 递归对左右两部分进行排序

3. 将左右两部分合二为一

大致思路是使用两个指针分别指向两部分的开头,再定义一个数组res存放两部分有序合并的结果

比较两个指针指向的值,将较小的存入res,对应的指针向后移动,较大的不动,按照这个规则重复直至两部分都存入了res即可

时间复杂度 O(nlogn)

递归地进行二分,一直到左右两部分各一个元素,一共可以分为logn层,然后进行合并

每层无论被范围多少部分,加起来都是n个元素,即每层合二为一的复杂度是O(n),得到整个算法的复杂度是O(nlogn)

image-20210710181032496

模板

int tmp[N];
void merge_sort(int q[], int l, int r)
{
    if(r <= l) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j])tmp[k++] = q[i++];
        else			tmp[k++] = q[j++];
   	while(i <= mid) 	tmp[k++] = q[i++];
    while(j <= r)	tmp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; ++i, ++j)	q[i] = tmp[j];
}

练手

AcWing 787. 归并排序

AcWing 788. 逆序对的数量

image-20210710224807873

我们求逆序对总数实际上就是上面三种情况的逆序对数量之和,逆序对两元素都在左半部分和都在右半部分交给递归处理即可,主要需要处理的就是跨越左半部分和右半部分的情况

这种情况下,我们在一旦在左半部分发现q[i]大于右半部分的q[j],那么在左半部分中q[i]及它后面的mid - i个元素都和q[j]构成逆序对,跨越情况的逆序对+ (mid - i + 1)

注意当数组有n个元素时,逆序对的数量最大的情况出现在 n - 1, n - 2, ..., 0这种序列的情况下,逆序对数量为(n - 1) + (n - 2) + ... + 1 + 0,数量级在 O ( n 2 ) O(n^{2}) O(n2),这种情况下注意有时需要将逆序对的计数变量定义为long long

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int q[N], tmp[N];
int n;

ll merge_sort(int q[], int l, int r)
{
    if(r <= l)  return 0;
    int mid = (l + r) >> 1;
    ll res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    if(q[i] <= q[j]) tmp[k++] = q[i++];
    else
    {
        res += mid - i + 1;
        tmp[k++] = q[j++];
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r)   tmp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i)  scanf("%d", &q[i]);
    cout << merge_sort(q, 0, n - 1) << endl;
    return 0;
}
这篇关于快速排序&归并排序&逆序对数量模板及分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!