这两个排序算法都要用到递归的代码,在使用递归的时候最重要的不要陷进每一环的重复中。抓住终止条件,在一个个的往上排,直至排到最后。
归并排序:就是将两组已经排序好的数组,归并为一个排序好的数组。
通俗的讲:归并排序有点像冒泡排序,不同的是,刚开始时它们都是两个先比较,而渐渐的成倍的增加比较个数。不过占内存,空间复杂度是o(n)。像是冒泡+递归。
但现实中,很少有两个已经排序好的数组。我们可以用分治思想把一混乱的数组分为子问题在合并。参考文章
image image示意图
image示意图
快速排序:就是取一组数据的最后一个元素,然后确定这个元素在整个数组中的位置,做法就是设置一个变量等于start,遍历一次,把大于这个数据的值都按顺序从start开始存放,直到遍历完之后,就可以找到这个元素的位置。
求第k大的数,或前k大的数都是用快排来解决,且时间复杂度为O(n)。
归并和快排的区别;
归并是先分区在计算,快排是先计算位置再分区。
网友评论