逆序对数代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】逆序对数

作者:英娴 / 发布于2016/4/21/ 461

//序列逆序对数,复杂度O(nlogn)
//传入序列长度和内容,返回逆序对数
//可更改元素类型和比较函数
#include <string.h>
#define MAXN 1000000
#define _cp(a,b) ((a)<=(b))
typedef int elem_t;
elem_t _tmp[MAXN];

int inv(int n,elem_t* a){
	int l=n>>1,r=n-l,i,j;
	int ret=(r>1?(inv(l,a)+inv(r,a+l)):0);
	for (i=j=0;i<=l;_tmp[i+j]=a[i],i++)
		for (ret+=j;j<r&&(i==l||!_cp(a[i],a[l+j]));_tmp[i+j]=a[l+j],j++);
	memcpy(a,_tmp,sizeof(elem_t)*n);
	return ret;
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　逆序对数　

同语言下

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

可能有用的

.SQL查询多列合并成一行用逗号隔开
.一行一行读取txt的内容
.C#动态修改文件夹名称(FSO实现，不移动文件)
.c# 移动文件或文件夹
.c#图片添加水印
.Java PDF转换成图片并输出给前台展示
.网站后台修改图片尺寸代码
.处理大图片在缩略图时的展示
.实现对图片上传的接收
.判断用户输入的是否为IP地址

英娴贡献的其它代码(25)

.文字浮在图片上方
.图片上传工具类
.通过管道获取一个进程的执行状态
.消去重复字符
.对图片进行马赛克处理，可控制模糊程度
.检查输入的字符值时候符合正则表达式规则
.垂直居中
.输出当前日期
.输入一个表得到这个表的查询结果
.逆序对数