本文档是C++代码片段,主要涉及一个控制台应用程序的入口点,名为"算法.cpp"。该程序定义了两个函数:`MERGE_INVESTIONS`和`COUNT_INVERSIONS`,以及一个`main`函数。程序的核心功能是计算数组`a`中元素的逆序对数量。 **1. `main` 函数** `main`函数是程序的起点,初始化了一个整型数组`a`,包含元素{5, 4, 3, 2, 1}。它调用`COUNT_INVERSIONS(a, 0, 4)`来计算整个数组的逆序对数,并将结果输出到控制台。逆序对是指对于数组中的每一对元素 `(i, j)`,如果 `i < j` 且 `a[i] > a[j]`,则认为这对是一个逆序对。 **2. `MERGE_INVERSIONS` 函数** 这个函数接收一个数组`a`、起始索引`p`、中间索引`q`和结束索引`r`作为参数。它的目的是合并两个子数组`a[p..q]`和`a[q+1..r]`,并计算合并过程中产生的逆序对数量。首先,通过创建临时数组`L`和`R`分别存储两个子数组,然后通过双指针`i`和`j`遍历它们。如果`L[i]`小于等于`R[j]`,则将`L[i]`放入原数组`a`并递增`i`;否则,将`R[j]`放入数组,打印出所有未匹配的逆序对,并递增`inversion`计数。最后返回总的逆序对数量。 **3. `COUNT_INVERSIONS` 函数** 这是一个递归函数,用于计算数组`a`在区间`[p, r]`内的逆序对总数。它采用分治策略,首先找到子区间`[p, q]`和`[q+1, r]`,然后递归地计算这两个子区间内的逆序对,最后将这些子区间的结果相加,并加上由`MERGE_INVERSIONS`函数计算得到的跨区间的逆序对。当`p`不小于`r`时,递归继续,直到子区间只有一个元素或为空。 这段代码提供了一个用于计算整数数组中逆序对的实用算法,它通过分割数组、合并子数组以及递归处理子问题的方式,有效地求解这个问题。这对于理解数据结构和排序算法中的基本概念非常有帮助,特别是对于那些涉及到递归和分治策略的问题。
//
#include "stdafx.h"
#include <iostream>
#define INFINITE 100000
using namespace std;
int MERGE_INVESTIONS(int a[],int p,int q,int r);
int COUNT_INVERSIONS(int a[],int p,int r);
int main()
{
int a[5]={5,4,3,2,1};
cout<<"\nthe inversion is:"<<COUNT_INVERSIONS(a,0,4)<<endl;
return 0;
}
int MERGE_INVERSIONS(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=new int [n1+1];
int *R=new int [n2+1];
int i,j,k;
for(i=0;i<n1;i++)
L[i]=a[p+i];
for(j=0;j<n2;j++)
R[j]=a[q+j+1];
L[n1]=INFINITE;
R[n2]=INFINITE;
i=0,j=0;
int inversion=0;
下载后可阅读完整内容,剩余2页未读,立即下载
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 计算机二级Python真题解析与练习资料
- 无需安装即可运行的Windows版XMind 8
- 利用gif4j工具包实现GIF图片的高效裁剪与压缩
- VFH描述子在点云聚类识别中的应用案例
- SQL解释器项目资源,助力计算机专业毕业设计与课程作业
- Java实现Windows本机IP定时上报到服务器
- Windows Research Kernel源码构建指南及工具下载
- 自定义Python插件增强Sublime文本编辑器功能
- 自定义Android屏幕尺寸显示及Ydpi计算工具
- Scratch游戏编程源码合集:雷电战机与猫鼠大战
- ***网上教材管理系统设计与实现详解
- Windows环境下VSCode及Python安装与配置教程
- MinGW-64bit编译opencv库适配Qt5.14
- JavaScript API 中文离线版手册(CHM格式)
- *** 8 MVC应用多语言资源管理技巧
- 互联网+培训资料深度解析与案例分析