现在的位置: 首页 > 面试题 > 正文

排序算法衍生问题

2022年01月10日 面试题 ⁄ 共 234字 ⁄ 字号 暂无评论
博客主机

本小节对本教程的排序算法做一个总结。

 

(1)归并排序和快速排序都使用了分治算法。

顾名思义,就是将原问题分割查能同等结构的子问题,之后将子问题逐一解决后,原问题也就得到了解决。

 

(2)逆序对的定义

如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对。我们可以使用本教程的归并思想求逆序对的数量。

 

(3)取数组中第 n 大的元素

并不需要对整个数组进行排序,使用快速排序的思路求数组中第 n 大元素算法复杂度为 O(n)。

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×