归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是 O(n)。正因为此它也没有快排应用广泛。快速排序算法虽然最坏情况下的时间复杂度是 O(n²),但是平均情况下时间复杂度都是 O(nlogn)。且快速排序算法时间复杂度退化到 O(n²) 的概率非常小,我们可以通过合理地选择基准值来避免这种情况。
什么是数组的逆序度
如果用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算就会很复杂。我们其实还有一种思路,通过有序度和逆序度这两个概念来进行分析。有序度是指数组中具有有序关系的元素对的个数,如下图所示:
所以对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是n\*(n-1)/2
,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。逆序度的定义正好跟有序度相反(默认从小到大为有序),所以满有序度 - 有序度 = 逆序度。
求数组的逆序度
数组的逆序度也就是数组的逆序对的个数,如果要求出来也是比较简单,直接暴力解法就可以,检查每一个数对,但是这样的时间复杂度为O(n²)。我们能否使用它更快捷的方法呢?其实是有的,那就是我们用归并排序的思路思路来解决这个问题,时间复杂度降到O(nlogn)。
如上图所示,对于归并排序,红线两边都是已经排好序的数组,此时做归并需要把1给挪到2的位置,意思就是1这个元素比2-8这一部分元素都大,所以无序度直接+4就达到了省时间的目的。接下来的步骤如图所示:
2会放在2的位置上,这也就意味着2比4以及4以后的元素都要小,那么2和4以及4以后的元素都组成了顺序对。当归并完成以后就求得了数组的逆序度:
1 | // merge函数求出在arr[l...mid]和arr[mid+1...r]有序的基础上, arr[l...r]的逆序数对个数 |
求数组中第N小的元素
其实这个问题是一个明显的Top K问题,但是我们除了用堆还能用其他方法吗?其实快速排序也可以解决这个问题,我们回顾一下快速排序的过程(《 快速排序及其优化 》),其实就是通过基准值每次把数组进行划分,我们只需要保留存在第N大的元素的那一部分即可,这么处理的话时间复杂度是O(n),复杂度 = n + n/2 + n/4 + n/8 + … ,所有看成是O(n)或者O(2n)的时间复杂度,但是我们需要注意的是需要使用随机化法,来确定基准值。
1 | public class QuickSortTopK { |
- 本文作者: Tim
- 本文链接: https://zouchanglin.cn/2020/04/11/3216229926.html
- 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。转载请注明出处!