归并排序
归并排序概念介绍：
cpp实现
利用归并排序计算逆序对的个数
cpp实现
归并排序是一种稳定的，时间复杂度nlog(n)的算法，其速度仅次于快排
概念介绍：
稳定:两个相同的数在排序时相对位置不会改变，例如1554排成1455，两个5的前后位置不发生变化，
归并操作：把两个顺序序列合并成一个顺序序列例如：
a={1,3,5,7}
b={2,4,6,8}
每个数组一个指针指向各自数组最前面的一个数，进行比较，小的放入temp数组，并将其往后移
ap=0,bp=0;
*ap=1, *bp=2;
第一次比较后，ap=1,bp=0
*ap=3 , *bp=2;以此类推
归并排序的本质是用分治，分：将数组分开；治：用归并法从一个元素的数组开始归并。举例如下：
原序列：1 4 6 2 3 7 1
第一次操作：{1 4}{2 6}{3 7}{1}比较三次
二：{1 2 4 6}{1 3 7}比较四次
三：{1 1 2 3 4 6 7} 比较六次，结束。
cpp实现
void merge_sort(int q[], int l, int r)
{
if (l >= r)return;
int mid = (l + r )/ 2;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;//从l到r
while (i <= mid && j <= r)
{
if (q[i] <= q[j])temp[k++] = q[i++];
else temp[k++] = q[j++];
}
while (i <= mid)//怕两个序列有没跑完的
{
temp[k++] = q[i++];
}
while (j <= r)
{
temp[k++] = q[j++];
}
for (i = 0, j = l;j <= r; i++, j++)
{
q[j] = temp[i];
}
}
利用归并排序计算逆序对的个数
首先先给出逆序对的定义：有i<j,q[i]>q[j]。
再看看归并排序的过程，我们很容易可以看出来，若有两个有序序列
asdfgh
zxcvbn
在归并操作中，将asd放入trmp中，意味着asd都小于z，而当第四个我选择z时，说明fgh都大于z，此时便有三个逆序对。
即在q[i]>q[j]时加上mid-i+1
cpp实现
*acwing788*
#include <iostream>
using namespace std;
int temp[1000000];
int q[1000000];
long long sum = 0;
void merge_sort(int q[], int l, int r)
{
if (l >= r)return;
int mid = (l + r )/ 2;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;//从l到r
while (i <= mid && j <= r)
{
if (q[i] <= q[j])temp[k++] = q[i++];
else temp[k++] = q[j++], sum += mid - i + 1;
}
while (i <= mid)//怕两个序列有没跑完的
{
temp[k++] = q[i++];
}
while (j <= r)
{
temp[k++] = q[j++];
}
for (i = 0, j = l;j <= r; i++, j++)
{
q[j] = temp[i];
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
merge_sort(q, 0, n - 1);
/*for (int i = 0; i < n; i++)
{
cout << q[i] << " ";
}*/
cout << sum << endl;
}
标签：sort,归并,int,mid,merge,排序,逆序
From： https://blog.csdn.net/2301_76462783/article/details/140486357