Menu

关于归并排序和快速排序的区别

2018年5月27日 - 算法,数据结构

归并排序和快速排序的区别

首先两者都采用了分治的思想,不同的是归并排序采用了二分的思想,而快速排序使用的是找一个数字,然后小的放左边,大的放右边的思想。

相比而言:归并排序分–的时候较简单,所以合的时候较复杂,同时也使用了辅助数组,而快速排序分的时候就比较复杂,两种排序算法都是不稳定的,时间复杂度都为O(nlog2N),归并排序空间复杂度为O(n),快排空间复杂度为O(1)

 

快速排序和归并排序的原理都是基于“分而治之”思想,即首先把待排序的元素分成两组,然后分别对这两组排序,最后把两组结果合并起来。

它们的区别在于,进行的分组策略不同,后面的合并策略也不同。

归并排序的分组策略是假设待排序的元素存放在数组中,那么其把数组前面一半元素作为一组,后面一半作为另一组。
快速排序是根据元素的值来分组,即大于某个值的元素放在一组,而小于的放在另外一组,该值称为基准。所以,对整个排序过程而言,基准值的挑选非常重要,如果选择不合适,太大或太小,那么所有元素都分在一组了。

总的来说,快速和归并排序,如果分组策略越简单,后面的合并策略就越复杂,因为快速排序在分组时,已经根据元素大小来分组了,而合并时,只需要把两个分组合并起来就行了,归并排序则需要对两个有序的数组根据大小合并。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: