苏北网
当前位置:首页>聚焦 >

归并排序的时间复杂度是什么?归并排序和快速排序的区别有哪些?_消息

时间 2023-07-05 16:03:26 来源:驱动中国网  

归并排序的时间复杂度:

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、归并排序每次将数组一分为二,快排每次将数组一分为三

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

相关阅读RELEVANT

  • 版权及免责声明:

内容搜集整理于网络,不代表本站同意文章中的说法或者描述。文中陈述文字和内容未经本站证实,其全部或者部分内容、文字的真实性、完整性、及时性本站不做任何保证或者承诺,并且本站对内容资料不承担任何法律责任,请读者自行甄别。如因文章内容、版权和其他问题侵犯了您的合法权益请联系邮箱:5 146 761 13 @qq.com 进行删除处理,谢谢合作!