当前位置:首页 » 操作系统 » 计数逆序算法

计数逆序算法

发布时间: 2023-11-13 05:46:48

① 怎么算逆序数急~~~!!!

可使用直接计数法,计算一个排列的逆序数的直接方法是逐个枚举逆序,同时统计个数。

举个例子:

标准列是1 2 3 4 5,那么 5 4 3 2 1 的逆序数算法

看第二个,4之前有一个5,在标准列中5在4的后面,所以记1个。

类似的,第三个 3 之前有 4 5 都是在标准列中3的后面,所以记2个。

同样的,2 之前有3个,1之前有4个,将这些数加起来就是逆序数=1+2+3+4=10。

(1)计数逆序算法扩展阅读:

其它算法:

1、归并排序

归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序,然后再将这两半合并起来。在合并的过程中(设l<=i<=mid,mid+1<=j<=h),当a[i]<=a[j]时,并不产生逆序数;

当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面的话,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数。

2、树状数组

由于树状数组的特性,求和是从当前节点往前求,所以,这里要查询插入当前数值之时,要统计有多少个小于该数值的数还没插入,这些没插入的数,都会在后面插入,也就形成了逆序数。

热点内容
androidhome键退出 发布:2025-07-14 00:30:03 浏览:505
我都世界模组反编译教程 发布:2025-07-14 00:29:45 浏览:644
法因数控钻床编程手册 发布:2025-07-14 00:18:26 浏览:490
gcc编译怎么知道错误的行数 发布:2025-07-14 00:06:21 浏览:383
压强算法 发布:2025-07-14 00:02:52 浏览:552
dns怎么配置端口 发布:2025-07-13 23:49:16 浏览:761
苹果服务器为什么停止响应 发布:2025-07-13 23:49:15 浏览:197
车载安卓导航usb接口在哪里 发布:2025-07-13 23:39:54 浏览:932
保定少儿编程培训班 发布:2025-07-13 23:30:04 浏览:82
亲缘关系算法 发布:2025-07-13 23:21:59 浏览:580