试题

对于任意一个序列a1,a2,a3...an，如果iaj则称为一个逆序对。例如：序列{1,2,7,5,6}中有两个逆序对<7,5>和<7,6>。排序的本质就是消除初始序列中的所有逆序对。

1)排序算法的性能分析中通常选择什么样的操作作为代表性操作?为什么?(2分)

2)请从消除逆序对的角度，说明为何冒泡排序、选择排序等采用相邻两元素比较 的排序算法在平均情况下的时间复杂度比快速非序和归并排序等要高。（3分）

3)设计一个你认为最优的算法（明确描述算法思想，不需要写程序），找出任意一个序列（元素互不相同)的逆序对个数，分析算法的复杂度。(5分)

【27考研辅导课程推荐】：27考研集训课程,VIP领学计划,27考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。