POJ-排序-归并排序与逆序对

2023-04-23,,

排序归并排序与逆序

一、概念

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

时间复杂度:O(nlogn)

二、算法描述

1.将数组拆分成单个元素,两两归并。
2.对于两组同向有序数组,首先判断两组数的首位的大小,并将较小的数保留到一个新数组中。
3.再比较较小组数的第二位和另一组数的第一位,仍然保留较小的数,这样就保证新数组的有序,需要注意的是当任意一组数为空时,就自然将另一组数的剩下数接到新数组后(因为剩下的树肯定比刚放进去的大)。

三、逆序对

逆序对问题设 A 为一个有 n 个数字的有序集 (n>1),其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 A[i], A[j]这个有序对称为 A 的一个逆序对,也称作逆序数。

例如,数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2),共4个。

四、归并排序与逆序对

因为在排序的合并过程中是将两组有序数进行比较,所以根据逆序对的定义,在数组下标 i 小于 j 时,如果有 a[i] 大于 a[j] 就可以知道下标 i 后面所有数都与 a[j] 构成逆序数,只需添加一句求和语句即可求出逆序数了;

例题 POJ1804 Brainman

解题思路

最简单的关于逆序对的题目,题目大意是给出一个序列,求最少移动多少步能使它顺序,规定只能相邻移动。
相邻移动的话,假设a,b 相邻,若a<b 交换会增加逆序数,所以最好不要做此交换;若a==b 交换无意义,也不要进行此交换;a>b时,交换会减少逆序,使序列更顺序,所以做交换。
由上可知,所谓的移动只有一种情况,即a>b,且一次移动的结果是逆序减1。假设初始逆序是n,每次移动减1,那么就需要n次移动时序列变为顺序。所以题目转化为直接求序列的逆序便可以了。

AC代码

#include<cstdio>
int a[];//存储数串的数组
int t[];//排好序的数组
int ans;//逆序对数 void merge(int l, int m, int r)//因为起点和终点不变,所以用i,j来表示可变的下标
{
int k = l, i = l, j = m + ;
while (i <= m && j <= r)//分解数组的首元素进行比较,两个数组分别为[l,m][m+1,r]
{
if (a[i] > a[j])//构成逆序对
{
t[k++] = a[j++];//将较小的元素加入排序后的数组,并移动到下一元素
ans = ans + m - i + ;//从i到middle的值都大于a[j],所以逆序对增加m-i+1
}
else
{
t[k++] = a[i++];
}
}
while (i <= m) t[k++] = a[i++];//若左边还有剩下的
while (j <= r) t[k++] = a[j++];
for (i = l; i <= r; i++)a[i] = t[i];//更新原数组为合并后的数组
} void mergeSort(int l,int r)//归排
{
if (l < r)//递归终止条件
{
int m = (l + r) / ;
mergeSort(l, m);
mergeSort(m + , r);//此时已经通过递归全部拆分
merge(l, m, r);//从单元素开始合并
}
} int main()
{
int T, n, cnt = ;
scanf("%d", &T);
while (T--)
{
ans = ;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
mergeSort(, n - );
printf("Scenario #%d:\n", cnt++);
printf("%d\n\n", ans);
}
return ;
}

例题 POJ2299 Ultra-QuickSort

解题思路

简单直接的归并排序求逆序数,和上一题一模一样。难点是n < 500000,所以答案用int32会WA,要用int64,用long long int也可以,取值范围一样的,printf函数对应I64d和lld。

AC代码

#include<cstdio>
const int N = ;
int a[N];
int t[N];
__int64 ans; void merge(int l, int m, int r)
{
int k = l, i = l, j = m + ;
while (i <= m && j <= r)
{
if (a[i] > a[j])
{
t[k++] = a[j++];
ans += m - i + ;
}
else
{
t[k++] = a[i++];
}
}
while (i <= m)t[k++] = a[i++];
while (j <= r)t[k++] = a[j++];
for (int i = l; i <= r; i++)a[i] = t[i];
} void mergeSort(int l, int r)
{
int m = (l + r) / ;
if (l < r)
{
mergeSort(l, m);
mergeSort(m + , r);
merge(l, m, r);
}
} int main()
{
int n;
scanf("%d", &n);
while (n != )
{
ans = ;
for (int i = ; i < n; i++)scanf("%d", &a[i]);
mergeSort(, n-);
printf("%I64d\n", ans);
scanf("%d", &n);
}
return ;
}

AC代码

POJ-排序-归并排序与逆序对的相关教程结束。

《POJ-排序-归并排序与逆序对.doc》

下载本文的Word格式文档,以方便收藏与打印。