归并排序白话讲解
归并排序
概念
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;
即先使每个子序列有序,再使子序列段间有序。
若将两个有序表合并成一个有序表,称为2-路归并。
使用前提
有序子列的归并
-
假设有上个表A 、B、C,将有序表A、B插入到C中
-
设置三个指针(并非必须为指针,可以是任何可以指定位置的结构)Aptr、Bptr、Cptr分别指向A、B、C表的起始位置
-
比较Aptr和Bptr将大的将其放置到Cptr的位置,然后将改变的+1
-
代码
-
A为待排序数组(A、B),TmpA为排序结果临时存放数组(C),L为左边起始位置(Aptr),R右边的起始位置(Bptr),REnd(右边数组的长度,左边的可以计算)
算法思路
归并排序是将两个或两个以上的有序表合并成一个新的有序表
将已有序的子序列合并,得到完全有序的序列;
即先使每个子序列有序,再使子序列段间有序。
适用场景
归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。
而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。
算法描述
递归法(Top-down)
分而治之
分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决
原理如下(假设序列共有n个元素):
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
伪码描述
生成临时存放空间,并向递归算法传入长度
递归算法:每次分半归并到临时数组,然后将临时数组写回待排数组
迭代法(Bottom-up)
迭代
将待排序列A进行不断的归并,归并结果存放在A与临时数组TmpA中(如果每次迭代都开辟临时数组将会造成巨大的空间占用),最后将排好序的结果返回在A中即可
原理如下(假设序列共有n个元素):
** 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两/一个元素
** 若此时序列数不是1个则将上述序列再次归并,形成ceil(n/4)个序列,每个序列包含四/三个元素
** 重复步骤2,直到所有元素排序完毕,即序列数为1
伪码描述
总控算法:控制迭代算法的执行
迭代算法