常用12大排序算法之八:归并排序(递归+非递归)

2017-04-22 22:01 阅读 1,987 次 评论 0 条

1.归并排序的基本思想

归并,是将两个或两个以上的有序表合并成一个新的有序表。

对象序列initList中两个有序表V[1]…V[m]和V[m+1]…V[n]。它们可归并成一个有序表,存于另一对象序列mergedList的V[1]…V[n]中。这种归并方法称为两路归并(2- way merging) 。

归并排序的特点和思想

(1)采用分而治之(divide and conquer)的策略;

(2)小的数据表排序比大的数据表要快;

(3)从两个已经排好序的数据表中构造一个排好序的数据表要比从两个未排序的书记表中构造要少许多步骤;

(4)它是一个稳定的排序算法;

(5)可以从递归、迭代两种思想实现。

 

2.归并排序的步骤

迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是:假设初始序列有n个对象,首先把它看n个长度为1的有序子序列,两两并归,重复上述操作,直到得到一个序列。特点是辅助空间占用多;稳定。

迭代的归并排序算法

与快速排序类似,归并排序算法也可以利用划分为子序列的方法递归实现。在递归的归并排序算法中,首先要把整个待排序序列划分为两个长度大致相等的部分,左子表和右子表。对子表分别递归地进行排序, 然后再把排好序的两个子表并归。特点是链表的归并排序方法的递归深度为O(log2n),对象排序码的比较次数为O(nlog2n);稳定。

递归的归并排序算法

(1)申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

(2)设定两个指针,最初位置分别为两个已经排序序列的起始位置;

(3)比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

(4)重复步骤3直到某一指针超出序列尾;

(5)将另一序列剩下的所有元素直接复制到合并序列尾。

 

3.归并排序算法复杂度分析

(1)时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能;

(2)空间复杂度为 O(n);

(3)比较操作的次数介于(nlogn) / 2和nlogn - n + 1;

(4)赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:0 (n);

(5)归并排序比较占用内存,但却是一种效率高且稳定的算法。

 

4.归并算法C语言源代码

 

 

5.归并算法C++源代码

(1)递归归并排序算法

 

(2)非递归归并排序算法

(3)二路递归归并排序算法

 

 

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之八:归并排序(递归+非递归) | 算法君

发表评论


表情