目录
- 一、概念
- 二、排序流程理解
- 三、代码实现
- 3.1主调函数
- 3.2 merge函数
- 四、性能分析
一、概念
归并是一种算法思想,是将两个或两个一上的有序表合并成一个长度较大的有序表。若一开始无序表中有n个元素,可以把n个元素看作n个有序表,把它们两两合并得到 ⌈ n / 2 ⌉ 个 \lceil n/2\rceil个 ⌈n/2⌉个长度为2或1(n为奇数时)的有序表,继续重复两两合并的操作,直到剩下一个有序表,即得到最终排序的结构,这是“二路归并排序”,还有多路的归并。
二、排序流程理解
给定一个序列如下:
1)不断地将当前序列平均分割成2个子序列,直到不能再分割(序列中只剩1个元素)
2)不断地将2个子序列合并成一个有序序列,直到最终只剩下1个有序序列
要点分析:
① 处理好边界和有序表分割位置选择问题
② 合并两个子序列的过程中,如何排序使合并后的序列是一个有序序列,称之为:merge
1、有序表分割的位置(排序使用到的参数:begin,mid,end)
初始时:
begin=0,mid=(begin+end)/2,end=length
规定:
左边表范围:[begin,mid)
右边表范围:[mid,end)
当无序表元素个数为偶数时,划分的左右子表元素个数相同,
当无序表元素个数为奇数时,划分的左右子表元素个数相差1,右子表多个一
不管奇偶情况如何,左子表元素个数为:mid-begin,右子表元素个数为:end-mid2、merge过程中我们使用一个辅助数组leftArray,把位于[begin,end)范围的表中左边部分[begin,mid)之间的元素拷贝到leftArray中,用leftArray表中元素和右边部分元素依次比较,小的放入原表(即:[begin,end) )中的左边部分,直到leftArray或右边部分的元素比较完,然后把剩余的没比较的直接拷贝到原表中即可,一次merge完成。
◼ li == 0,le == mid – begin
◼ ri == mid,re == end
三、代码实现
3.1主调函数
void sort(int *nums,int begin,int end){if(end-begin<=1) return;//只有一个元素不用排序int mid=(begin+end)/2;//或(begin+end)>>1sort(nums,begin,mid);sort(nums,mid.begin);merge(nums,begin,mid,end);
}
3.2 merge函数
void merge(int *nums,int begin,int mid,int end){int li=0;int le=mid-begin;int ri=mid;int re=end;int ai=begin;int leftArray=(int*)malloc(le*sizeof(int));//辅助数组//初始化辅助数组for(int i=li;i<le;i++){leftArray[i]=nums[begin+i];//begin~end之间左边部分拷贝到夫leftArray}//在原存储空间上给两个有序子表重新排序(逻辑上是合并为一个有序表),两种可能:左边指针先走完(ri>=re)或右边指针先走完。//若左边先走完则直接把leftArray中li指针指向的及之后的元素复制到原存储空间(nums);若右边先走完,则结束while(li<le){if(ri<re&&nums[ri]<leftArray[li]){nums[ai++]=nums[ri++];//拷贝左边部分的元素到nums[ai]}else{nums[ai++]=leftArray[li++];//拷贝右边部分的元素到nums[ai]}}
}
四、性能分析
空间效率: merge函数中使用的辅助空间是n/2个单元,即算法的空间复杂度:O(n)
时间效率: 每趟归并的时间复杂度是O(n),总共需要进行 ⌈ l o g 2 n ⌉ \lceil log_2n\rceil ⌈log2n⌉趟归并,总的时间复杂度:O(nlog2n)
稳定性: 不会改变相同关键字记录的相对次序(看merge函数中while循环的处理部分可知),因此二路归并排序是稳定的排序算法