住房和城乡建设部网站标准下载,网店设计方案,北京金港建设股份有限公司网站,企业网站建设网页算法对比#xff1a;
算法时间复杂度适合场景冒泡排序、插入排序、选择排序O(n2)小规模数据归并排序、快速排序O(nlogn#xff09;大规模数据
归并排序和快速排序都用到了分治思想#xff0c;非常巧妙。我们可以借鉴这个思想#xff0c;来解决非排序的问题#xff0c;比如…算法对比
算法时间复杂度适合场景冒泡排序、插入排序、选择排序O(n2)小规模数据归并排序、快速排序O(nlogn大规模数据
归并排序和快速排序都用到了分治思想非常巧妙。我们可以借鉴这个思想来解决非排序的问题比如如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素
归并排序
使用分治思想大问题分解为小问题分而治之小问题解决了大问题也就解决了。 归并排序的递推公式:
递推公式
merger_sort(p..r) merge(merger_sort(p..q),merger_sort(q1..r))
终止条件
pr 不再继续分解
归并排序的伪代码
merge_sort(A,n){merge_sort_c(A,0,n-1)
}
merge_sort_c(A,p,r){if p r then returnq (pr)/2;//分治递归merge_sort_c(A,p,q)merge_sort_c(A,q1,r)//合并merge(A[p...r],A[p...q],A[q1...r])}
merge函数的实现思路
申请一个临时数组 tmp大小与 A[p...r]相同。我们用两个游标 i 和 j分别指向 A[p...q]和 A[q1...r]的第一个元素。比较这两个元素 A[i]和 A[j]如果 A[i]A[j]就把 A[i]放入到临时数组 tmp并且 i 后移一位否则将 A[j]放入到数组 tmpj 后移一位。继续上述比较过程直到其中一个子数组中的所有数据都放入临时数组中再把另一个数组中的数据依次加入到临时数组的末尾这个时候临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p...r]中。
merge函数的伪代码 merge(A[p...r], A[p...q], A[q1...r]) {var i : pj : q1k : 0 // 初始化变量i, j, kvar tmp : new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组while iq AND jr do {if A[i] A[j] {tmp[k] A[i] // i等于i:i1} else {tmp[k] A[j]}}// 判断哪个子数组中有剩余的数据var start : iend : qif jr then start : j, end:r// 将剩余的数据拷贝到临时数组tmpwhile start end do {tmp[k] A[start]}// 将tmp中的数组拷贝回A[p...r]for i:0 to r-p do {A[pi] tmp[i]}
}
归并排序性能分析
稳定排序、非原地排序、时间复杂度为 O(nlogn)归并排序的执行效率与要排序的原始数组的有序程度无关所以其时间复杂度是非常稳定的不管是最好情况、最坏情况还是平均情况时间复杂度都是 O(nlogn)。空间复杂度为O(n)。
快速排序
快排的思想是这样的如果要排序数组中下标从 p 到 r 之间的一组数据我们选择 p 到 r 之间的任意一个数据作为 pivot分区点。我们遍历 p 到 r 之间的数据将小于 pivot 的放到左边将大于 pivot 的放到右边将 pivot 放到中间。经过这一步骤之后数组 p 到 r 之间的数据就被分成了三个部分前面 p 到 q-1 之间都是小于 pivot 的中间是 pivot后面的 q1 到 r 之间是大于 pivot 的。根据分治、递归的处理思想我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q1 到 r 之间的数据直到区间缩小为 1就说明所有的数据都有序了。
快排的递推公式 递推公式
quick_sort(p…r) quick_sort(p…q-1) quick_sort(q1… 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 returnq partition(A, p, r) // 获取分区点quick_sort_c(A, p, q-1)quick_sort_c(A, q1, r)
}
归并排序中有一个 merge() 合并函数我们这里有一个 partition() 分区函数。partition() 分区函数实际上我们前面已经讲过了就是随机选择一个元素作为 pivot一般情况下可以选择 p 到 r 区间的最后一个元素然后对 A[p...r]分区函数返回 pivot 的下标。
如果不考虑空间消耗的我们申请2个临时数组X,Y遍历A[p...r]将小于pivot的元素复制到X,大于pivot的元素复制到Y最后再将数组X和Y的数据顺序拷贝到A[p...r]即可。示意图 如果我们希望快排是原地排序算法那它的空间复杂度得是 O(1)那 partition() 分区函数就不能占用太多额外的内存空间我们就需要在 A[p...r]的原地完成分区操作
/**游标i对应的是什么数字并不关心它只是一个分界线游标i前面的区间都是小于pivot的后面遍历到某个数时如果小于pivot那么就跟当前的游标i进行数字交换然后游标i 游标j是遍历游标一直往前走 游标i是分界游标只有出现交换操作才会往前走
**/
partition(A, p, r) {pivot : A[r]i : pfor j : p to r-1 do {if A[j] pivot {swap A[i] with A[j]i : i1}}swap A[i] with A[r]return i快排性能分析
通过游标 i 把 A[p...r-1]分成两部分。A[p...i-1]的元素都是小于 pivot 的我们暂且叫它“已处理区间”A[i...r-1]是“未处理区间”。我们每次都从未处理的区间 A[i...r-1]中取一个元素 A[j]与 pivot 对比如果小于 pivot则将其加入到已处理区间的尾部也就是 A[i]的位置。在数组某个位置插入元素需要搬移数据非常耗时。当时我们也讲了一种处理技巧就是交换在 O(1) 的时间复杂度内完成插入操作。借助这个思想只需要将 A[i]与 A[j]交换就可以在 O(1) 时间复杂度内将 A[j]放到下标为 i 的位置。因此快排不是稳定排序算法 快排和归并排序区别归并排序是自顶向下先处理子问题然后再合并快排是自底向上先分区然后再处理子问题。 归并排序虽然是稳定排序但是是非原地排序而快速可以实现原地排序。归并排序的时间复杂度跟原数据的是否有序无关始终是O(nlogn)快速排序的时间复杂度在极端情况下如果数组中的数据原来已经是有序的了比如 13568。如果每次选择最后一个元素作为 pivot那每次分区得到的两个区间都是不均等的。需要进行大约 n 次分区操作才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素这种情况下快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。但是也有很多方法将这个概率降到很低。所以实际中快排应用最多而归并排序很少使用。
标题解答
快排核心思想就是分治和分区我们可以利用分区的思想来解答开篇的问题O(n) 时间复杂度内求无序数组中的第 K 大元素。比如4 2 5 12 3 这样一组数据第 3 大元素就是 4。
我们选择数组区间 A[0...n-1]的最后一个元素 A[n-1]作为 pivot对数组 A[0...n-1]原地分区这样数组就分成了三部分A[0...p-1]、A[p]、A[p1...n-1]。如果 p1K那 A[p]就是要求解的元素如果 Kp1, 说明第 K 大元素出现在 A[p1...n-1]区间我们再按照上面的思路递归地在 A[p1...n-1]这个区间内查找。同理如果 Kp1那我们就在 A[0...p-1]区间查找。
