归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。需要额外的存储空间,时间复杂度: T(n) = Θ(nlgn)。
基本原理及实现
基本原理:使用递归、分治思想,将待排序数组分割成字数组,将排序后的字数组合并。
- ① 当数组只包含一个元素时,直接返回该元素即可。
- ② 取数组中间位置元素,递归调用左侧和右侧数组,进行归并排序。
- ③ 将左侧和右侧排序后的有序数组进行合并。
使用Swift进行功能实现,如下:
1 | /** |
测试用例及结果
1 | //测试用例 |
1 | //测试用例 |
本文标题:归并排序
文章作者:梁通
发布时间:2016-04-26
最后更新:2020-08-03
原始链接:http://www.liangtong.site/2016/04/26/algorithm_20160426_sort_merge/
版权声明:Copyright© 2016-2020 liangtong 版权所有