归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。本文将通过动图详解归并排序的原理及实现,需要的可以参考一下
归并排序
归并排序主要分成两部分实现,分、合两部分,分是把数组分成两半,再递归的对子数组进行 分 操作,直到分成一个个单独的数。合是把两个数组合并为有序数组,在对有序数组进行合并,直到全部子数组合并为一个完整的数组。
算法原理
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤c直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
动图演示
代码实现
复杂度
- 时间复杂度:O(nlogn)
- 空间复杂度:O(n)
到此这篇关于图解Java经典算法归并排序的原理与实现的文章就介绍到这了,更多相关Java归并排序内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网!