每日信息:归并排序的时间复杂度是什么?归并排序和快速排序的区别有哪些?

来源:驱动中国网时间:2023-07-05 16:27:18

归并排序的时间复杂度:

1、归并操作的工作原理包括申请空间使其大小为两个已经 排序序列之和,该空间用来存放合并后的序列,设定两个指针最初位置分别为两个已经排序序列的起始位置,比较两个指针所指向的元素,选择相对小的元素放入到合并空间并移动指针到下一位置,重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾。

2、归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用,将已有序的子序列合并得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序,若将两个有序表合并成一个有序表称为二路归并。

3、按数量级递增排列,常见的时间复杂度有常数阶O(1)对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),……k次方阶O(nk)指数阶O(2n),随着问题规模n得不断增大。

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

1、先分解再合并:归并排序先递归分解到最小粒度,然后从小粒度开始合并排序,自下而上的合并排序;

2、边分解边排序:快速排序每次分解都实现整体上有序,即参照值左侧的数都小于参照值,右侧的大于参照值;是自上而下的排序;

3、归并排序不是原地排序,因为两个有序数组的合并一定需要额外的空间协助才能合并;

4、快速排序是原地排序,原地排序指的是空间复杂度为O(1);

5、归并排序每次将数组一分为二,快排每次将数组一分为三

标签: 有效排序算法 分治法典型应用 二路归

责任编辑:FD31
上一篇:个人养老金可以买哪些基金?个人养老金有必要买吗?
下一篇:最后一页

精彩图集(热图)

热点图集

最近更新

信用中国

  • 信用信息
  • 行政许可和行政处罚
  • 网站文章