文章来源于极客时间前google工程师−王争专栏。
冒泡排序、插入排序、选择排序三种排序算法,时间复杂度都是O(n^2),比较高,适合小规模数据的排序。
归并排序和快速排序两种时间复杂度O(nlogn)的排序算法,适合大规模的数据排序,比上述三种更常用。
归并排序和快速排序都用到了分治思想,非常巧妙。我们可以借助这个思想,解决排序问题:如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素?
归并排序核心思想:如果要排序一个数组,先把数组从中间分为前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就有序了。
归并排序使用的就是分治思想。分而治之,大问题分解成小问题来解决。分治思想与递归思想很像。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。
如何用递归代码来实现归并排序?
归并排序递推公式
递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件:
p >= r 不用再继续分解
伪代码实现如下:
// 归并排序算法, A 是数组,n 表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取 p 到 r 之间的中间位置 q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
merge函数实现思路:申请临时数组tmp,大小与A[P…r]相同。用两个游标i和j,比较移动。最后tmp拷贝到原数组。如图所示:
代码实现如下:
merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p,j := q+1,k := 0 // 初始化变量 i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++ 等于 i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判断哪个子数组中有剩余的数据
var start := i,end := q
if j<=r then start := j, end:=r
// 将剩余的数据拷贝到临时数组 tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 将 tmp 中的数组拷贝回 A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}
思考:merge()合并函数借助哨兵,代码会简洁很多。
合并过程关键看merge函数,把之前数组的元素先放入tmp数组,可以保证值相同的元素前后顺序不变。所以归并排序是一个稳定的排序算法。
可以理解为如何分析递归代码的时间复杂度
T(a) = T(b) + T(c) + K
求解问题a时间T(a),求解问题b,T(b)。求解问题c,T©,K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。
从刚刚的分析,我们可以得到一个重要的结论:不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。
假设对n个元素进行归并排序需要的时间是T(n),分解成两个子数组排序的时间都是T(n/2)。merge()函数合并两个有序子数组的时间复杂度为O(n),所以计算归并排序的时间复杂度就是:
T(1) = C; n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1
分解推导计算过程:
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
通过这样一步一步分解推导,我们可以得到 T(n) = 2kT(n/2k)+kn。当 T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们得到 k=log2n 。我们将k 值代入上面的公式,得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话,T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。
归并排序时间复杂度非常稳定,不管最好、最坏、还是平均,时间复杂度都是O(nlogn)。
归并排序没有像快排那样应用广泛,因为它有一个致命的“弱点”,归并排序不是原地排序算法。
合并过程中需要借助额外的存储空间。
借助递归复杂度分析方法,空间复杂度是nlogn,但是空间复杂度不能像时间复杂度那样累加。合并完成之后,临时开辟的内存空间就被释放掉了。任意时刻,CPU只会有一个函数在执行,也就只会有一个临时内存空间在使用。所以空间复杂度为n。
快排利用的也是分治思想,但是与归并思路完全不一样。
思想:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为povot(分区点)。
根据分治、递归的处理思想,递归公式如下:
递推公式:
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件:
p >= r
公式转化为代码,伪代码如下:
// 快速排序,A 是数组,n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
归并有merge()函数,这里有partition()分区函数。随机选择一个元素作为pivot(一般情况下,可以选择p到r区间的最后一个元素),然后对A[p…r]分区,函数返回pivot的下标。
不考虑空间消耗,可以申请两个临时数组
这样就不是原地排序算法了,所以我们要原地完成分区操作。代码如下:
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i
public int partition(int[] A,int p,int r){
//取最后一个元素作为中间点
int pivot = A[r];
int i = p;
//遍历右区间
for(int j = p;j
例如6,8,7,8,3,5,9,4,进过第一次分区操作之后,两个6的顺序会发生改变。所以快速排序并不是一个稳定给的排序算法。
快排和归并都是用的分治思想,递推公式和递推代码也非常相似,它们区别在哪里?
快排是一种原地、不稳定的排序算法。现在我们分析时间复杂度。
快排也是用递归实现,递归总结的公式,还是适用。如果每次分区,都能刚好将数组分成大小接近相等的两个小区间,那快排的时间复杂度递推公式与归并相同看,也是nlogn。
T(1) = C; n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1
如果数组已经有序,每次分区不均等,需要大约n次分区,每次分区平均扫描n/2个元素,这种情况,快排时间复杂度从nlogn退化成n^2了。
T(n) 在大部分情况下的时间复杂度都可以做到O(nlogn),只有在极端情况下,才会退化到 O(n2)。而且,我们也有很多方法将这个概率降到很低,如何来做?
快排核心思想就是分治和分区,可以利用分区的思想,来解答开篇问题:O(n)时间复杂度内求无序数组中的第K大元素。比如4,2,5,12,3这样一组数据,第三大元素就是4。
我们选择数组区间A[0…n-1]、A[n-1]作为pivot,对数组A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[P]、A[p+1…n-1]。
如果p+1 = K,那 A[p] 就是要求解的元素;如果 K>p+1, 说明第K 大元素出现在 A[p+1…n-1] 区间,我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理,如果K
我们再来看,为什么上述解决思路的时间复杂度是 O(n)?
第一次分区查找,我们需要对大小为n的数组执行分区操作,需要遍历n个元素。第二次分区查找,我们只需要对大小为n/2的数组执行分区操作,需要遍历n/2个元素。依次类推,分区遍历元素的个数分别n/2、n/4、n/8、n/16.……直到区间缩小为 1。
如果我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1。这是一个等比数列求和,最后的和等于2n-1。所以,上述解决思路复杂度就是O(n)。
每次去数组中最小值,将其移动到数组的最前面,然后在剩下的数中继续找最小值,以此类推,执行K次,找到的数据不就是第K大元素了吗?
上述做法时间复杂度是O(k*n),当k等于n时,最坏情况下时间复杂度就是O(n^2)了。
现在你有 10 个接口访问日志文件,每个日志文件大小约300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件,合并为1个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB,你有什么好的解决思路,能“快速”地将这10 个日志文件合并吗?
基本思路:先构建十条io流,分别指向十个文件,每条io流读取对应文件的第一条数据,然后比较时间戳,选择出时间戳最小的那条数据,将其写入一个新的文件,然后指向该时间戳的io流读取下一行数据,然后继续刚才的操作,比较选出最小的时间戳数据,写入新文件,io流读取下一行数据,以此类推,完成文件的合并,这种处理方式,日志文件有n个数据就要比较n次,每次比较选出一条数据来写入,时间复杂度是O(n),空间复杂度是O(1),几乎不占用内存