归并排序——逆序数对的统计

2024-06-10 11:20
文章标签 统计 归并 排序 序数

本文主要是介绍归并排序——逆序数对的统计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

逆序数对的统计

题目描述

运行代码

#include <iostream>
using namespace std;
#define LL long long 
const int N = 1e5 + 5;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r)
{if (l >= r)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 (i = l, j = 0; i <= r; i ++, j ++ )q[i] = tmp[j];  return res;
}
int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) 
scanf("%d", &a[i]);    cout << merge_sort(a, 0, n - 1) << endl;  return 0;
}

代码思路

宏定义与常量

  • #define LL long long:定义LLlong long类型的别名,用于存储较大的整数,例如逆序对的数量。
  • const int N = 1e5 + 5;:定义数组的最大容量,适用于最多100,005个元素的数组。

函数merge_sort此函数递归地将数组分成更小的部分,然后合并这些部分,同时计算逆序对总数。

  • 参数q[]是要排序的数组,lr分别是当前子数组的左右边界(索引)。
  • 基础情况:当左边界大于等于右边界时(即子数组只有一个或没有元素),返回0,表示该子数组没有逆序对。
  • 分解:计算中间索引mid,递归地对左右两部分[l, mid][mid+1, r]进行排序并计算逆序对,将结果累加到res中。
  • 合并
    • 初始化辅助数组tmp和三个指针k, i, j。当i未超过midj未超过r时,比较q[i]q[j]的大小:
      • 如果q[i] <= q[j],说明当前元素不会形成新的逆序对,将q[i]放入tmp,并移动ik
      • 否则,所有q[i]q[mid]之间的元素都比q[j]大,因此增加了mid - i + 1个逆序对,将q[j]放入tmp,移动jk
    • 分别处理剩余的元素,将它们依次放入tmp。将tmp中的元素复制回原数组q
  • 返回值:最终返回整个数组排序过程中的逆序对总数res
  • 主函数main读取数组长度n。通过循环读取数组a中的每个元素。调用merge_sort函数,传入数组a和其边界(0和n-1),输出计算得到的逆序对总数。

改进思路

  • 使用指针直接操作数组:在mergeSortAndCount函数中,直接使用指针ijk而非索引,这在某些情况下可以略微提高访问效率。
  • 保持数组作为参数:继续使用原生数组作为函数参数,保持与原始代码结构的一致性。
  • 代码格式和可读性:调整代码格式,确保良好的可读性和一致性,比如增加必要的空格和换行。
  • 去除不必要的类型别名:保留int64_t作为长整型的别名,因为它清晰地表达了数据类型的目的。

改进代码

#include <iostream>
using namespace std;
typedef long long int64_t;
// 使用指针代替数组索引来优化访问速度
int64_t mergeSortAndCount(int a[], int temp[], int left, int right) {if (left >= right) return 0;   int mid = left + (right - left) / 2;   // 递归排序并计数int64_t inv_count = mergeSortAndCount(a, temp, left, mid);inv_count += mergeSortAndCount(a, temp, mid + 1, right);   // 合并阶段计算逆序对int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {if (a[i] <= a[j]) {temp[k++] = a[i++];} else {inv_count += mid - i + 1;temp[k++] = a[j++];}}  // 复制剩余元素while (i <= mid) temp[k++] = a[i++];while (j <= right) temp[k++] = a[j++];    // 将排序结果复制回原数组for (int p = left; p <= right; ++p) a[p] = temp[p];   return inv_count;
}
int main() {const int N = 1e5 + 10;int a[N], temp[N];int n;scanf("%d", &n);   for (int i = 0; i < n; ++i) scanf("%d", &a[i]);   int64_t inv_count = mergeSortAndCount(a, temp, 0, n - 1);cout << inv_count << endl;   return 0;
}

其他方法(使用向量) AI生成

#include <iostream>
#include <vector>using namespace std;
using int64_t = long long;// 合并排序并计数逆序对
int64_t mergeSortAndCount(vector<int>& array, vector<int>& temp, int left, int right) {if (left >= right) return 0;int mid = left + (right - left) / 2;// 递归排序左右两边,并计算逆序对int64_t inv_count = mergeSortAndCount(array, temp, left, mid);inv_count += mergeSortAndCount(array, temp, mid + 1, right);// 合并阶段计算逆序对int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (array[i] <= array[j]) {temp[k++] = array[i++];} else {inv_count += mid - i + 1; // 计算逆序对temp[k++] = array[j++];}}// 处理剩余元素while (i <= mid) temp[k++] = array[i++];while (j <= right) temp[k++] = array[j++];// 将排序结果复制回原数组copy(temp.begin(), temp.begin() + k, array.begin() + left);return inv_count;
}int main() {int n;cin >> n;vector<int> a(n);for (int& elem : a) cin >> elem;vector<int> temp(n); // 临时数组用于合并cout << mergeSortAndCount(a, temp, 0, n - 1) << endl;return 0;
}
  1. 添加函数注释:解释每个函数的作用,特别是merge_sort中的逻辑。
  2. 使用更明确的变量名:如将q[]改为array[],使代码意图更清晰。
  3. 去除全局变量:尽量减少全局变量的使用,改用函数参数传递。
  4. 优化类型别名的可读性:将LL改为更明确的别名,如typedef long long int64_t;
  5. 使用C++风格的输入输出:完全替换scanfprintfcincout

归并、插入和冒泡排序比较

归并排序

  • 优点:时间复杂度在平均和最坏情况下都为 ,性能比较稳定,适合大规模数据排序。
  • 缺点:需要额外的空间用于合并。

插入排序

  • 优点:对于接近有序的数据表现非常好,在小规模数据或部分有序数据上效率可能较高,代码简单。
  • 缺点:最坏情况时间复杂度为 。

冒泡排序

  • 优点:实现简单。
  • 缺点:时间复杂度较差,也是 。

一般来说,在数据规模较大且对性能要求较高时,归并排序通常表现更好。但如果数据规模较小或者数据有一定的特殊性(如接近有序),插入排序可能更合适。而冒泡排序相对来说在大多数情况下效率较低,较少被优先选用。

使用归并排序解决逆序数对统计问题思路:

在归并排序的合并过程中,当我们比较左右两部分元素时,左边部分一个较大元素如果出现在右边部分较小元素之前,那么就构成一个逆序数对。

当左边当前元素大于右边当前元素时,由于左右两边都是已排序的,那么左边该元素之后的所有元素与右边当前元素都构成逆序数对,数量为左边当前未处理元素的数量。我们可以在合并的同时统计这样的逆序数对数量。通过递归地执行归并排序,不断在合并过程中累加逆序数对的数量,最终就能得到总的逆序数对数量。

例如,假设有数组 [3, 1, 4, 2],在第一次合并 [3] 和 [1] 时,因为 3 大于 1,此时就找到一个逆序数对,然后继续递归合并其他部分并统计。

这篇关于归并排序——逆序数对的统计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1048025

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In