算法之逆序对

算法之逆序对

逆序对问题

​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。

  1. 列出数组{2, 3, 8, 6, 1}的5个逆序对
  2. 由集合{1, 2, ..., n}中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
  3. 插入排序的运行时间与输入数组中的逆序对的数量有什么关系?
  4. 给出一个求在n个元素的任何排列中逆序对数量的算法,最坏时间复杂度为: \(\Theta\)(nlgn)
  5. 根据定义易得,逆序对为:(2, 1)、(3, 1)、(8, 6)、(8, 1)、(6, 1)
  6. 当数组元素恰好为n个元素从大到小排列时,拥有最多的逆序对。此时逆序对为: (n - 1) + (n -2) + (n - 3) + ... + 1 = n(n - 1) / 2
  7. 根据插入排序的实现过程,不难得出每次从未排序数组选择一个值arr[j]插入已排序数组的时候,所需要的移动次数,即为以arr[j]为右侧值的逆序对的个数。这个特性也可以设计出一个时间复杂度为: \(\Theta\)(\(n^2\))的算法。当然这种指数级别复杂度的算法我们直接PASS
  8. 不难想到\(\Theta\)(nlgn)算法复杂度的归并排序。其实归并排序在分治的时候不会改变逆序对的个数。只有在合并的时候,才会因为逆序对的出现导致右侧提前被合入原数组。其实修改点主要在两个方面:
  • 声明一个全局变量用来存储总的次数
  • 在右侧提前被合入原数组的时候对总次数进行累加(只需要改归并排序的merge方法, 归并排序请参照http://www.cnblogs.com/Kidezyq/p/8379267.html

具体源代码如下:

private static int count;

private static void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
    /**
     * 合并策略: 
     * 1. 新建两个数组,分别存取左半部分排好序的数组和右半部分排好序的数组
     * 2. 分别从左右两个数组最开始下标开始遍历,选取较小的依次放入原数组对应位置
     * 3. 最终如果左右数组中有一个已经遍历完成,另一个数组所剩的元素直接放入元素组后面部分即可
     */
    // STEP1
    int[] leftArr = new int[midIndex - startIndex];
    int[] rightArr = new int[endIndex - midIndex];
    System.arraycopy(arr, startIndex, leftArr, 0, leftArr.length);
    System.arraycopy(arr, midIndex, rightArr, 0, rightArr.length);
    
    // STEP2
    int k = startIndex; // 存储原数组中的下标
    int i = 0;          // 存储左边数组的下标
    int j = 0;          // 存储右边数组的下标
    while (i < leftArr.length && j < rightArr.length) {
        // 将较小的元素复制到元素组对应下标k,并且移动较小元素所在数组下标
        if (leftArr[i] < rightArr[j]) {
            arr[k++] = leftArr[i++];    
        } else {
            // 此时说明 arr[i]到arr[leftArr.length - 1]的值都比arr[j]大,即此时以arr[j]结尾的逆序对个数为: 
            count += leftArr.length - i;
            arr[k++] = rightArr[j++];
        }
    }
    
    // STEP3
    if (i < leftArr.length) {
        System.arraycopy(leftArr, i, arr, k, leftArr.length - i);
    } else if (j <= rightArr.length) {
        System.arraycopy(rightArr, j, arr, k, rightArr.length - j);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

希尔排序

希尔排序的时间复杂度,最好的情况下仍然是正序时,可达到O(n),平均复杂度为O(nlogn)。 算法思想: 采用跳跃式处理数组,使得数组粗粒度的实现基本有序。...

1925
来自专栏阿凯的Excel

Excel的匹配函数全应用

今天会和大家分享日常使用频率最高匹配函数用法,谈到匹配函数,首先想到的就是Vlookup,嗯,今天就是要分享Vlookup和他的小伙伴们的应用。 ? ...

3044
来自专栏青玉伏案

算法与数据结构(十二) 散列(哈希)表的创建与查找(Swift版)

散列表又称为哈希表(Hash Table), 是为了方便查找而生的数据结构。关于散列的表的解释,我想引用维基百科上的解释,如下所示: 散列表(Hash tab...

19710
来自专栏Flutter入门

有趣的正则表达式

听到正则表达式,大家一定不会陌生。工作项目中也经常使用正则表达式来校验文本的是否匹配规则。通常都会直接上网找寻各种格式输入的正则匹配式。比如电话/邮件等等。

863
来自专栏青青天空树

正则表达式在密码强度匹配中的使用

  今天领导让我写几个正则表达式来对密码做强度验证,听到写正则表达式内心是这样的感觉(哈哈,三分钟搞定,今天又可以打鱼了)。需求如下:密码组成只能是数字,字母,...

913
来自专栏小灰灰

# Java 一步一步实现高逼格的字符串替换工具(二)

Java 一步一步实现高逼格的字符串替换工具(二) 上一篇实现了一个用于字符串替换的方法,主要是利用 正则 + jdk的字符串替换,本篇则会再之前的基础上...

1896
来自专栏C语言及其他语言

C语言经典笔试题

1.以下程序的结果是什么? ? A: main()函数里的i是一个未定义值 B: main()函数的i为1 C: 编译器不允许这种写法 D: main()里i的...

3377
来自专栏进击的程序猿

Say No to Loop!

本文会介绍下Eloquent\Collection,这个是什么呢?这是我们平常使用Eloquent中get,all返回的结果集。

703
来自专栏前端新视界

常用的 JS 排序算法整理

关于排序算法的问题可以在网上搜到一大堆,但是纯 JS 版比较零散,之前面试的时候特意整理了一遍,附带排序效率比较。 //1.冒泡排序 var bubbleSo...

1889
来自专栏企鹅号快讯

R包系列——stringr包

stringr包是Hadley Wickham大神贡献的R包之一,主要用于字符串的处理。对于经常需要对数据进行预处理的分析人员来说,简直是一把“利器”,可谓是上...

1996

扫码关注云+社区