美文网首页
o(nlogn)的归并排序和快速排序

o(nlogn)的归并排序和快速排序

作者: isLJli | 来源:发表于2020-06-27 11:42 被阅读0次

    这两个排序算法都要用到递归的代码,在使用递归的时候最重要的不要陷进每一环的重复中。抓住终止条件,在一个个的往上排,直至排到最后。

    归并排序:就是将两组已经排序好的数组,归并为一个排序好的数组。

    通俗的讲:归并排序有点像冒泡排序,不同的是,刚开始时它们都是两个先比较,而渐渐的成倍的增加比较个数。不过占内存,空间复杂度是o(n)。像是冒泡+递归。

    但现实中,很少有两个已经排序好的数组。我们可以用分治思想把一混乱的数组分为子问题在合并。参考文章

    image image

    示意图

    image

    示意图

    快速排序:就是取一组数据的最后一个元素,然后确定这个元素在整个数组中的位置,做法就是设置一个变量等于start,遍历一次,把大于这个数据的值都按顺序从start开始存放,直到遍历完之后,就可以找到这个元素的位置。

    求第k大的数,或前k大的数都是用快排来解决,且时间复杂度为O(n)。

    归并和快排的区别;

    归并是先分区在计算,快排是先计算位置再分区。

    相关文章

      网友评论

          本文标题:o(nlogn)的归并排序和快速排序

          本文链接:https://www.haomeiwen.com/subject/mlmmfktx.html