Yan`s Notepad

--- My Notepad......Articles, tools and etc.
归并排序原理和C语言实现
归并排序是一个稳定的排序算法。除快速排序外,另一种速度仅次于快速排序的算法便是归并排序。
归并排序(merge sort),以分治法完成。所谓先分后治的思想。它会把一个序列拆分,一直到单个序列,再将这些序列合并,合并的同时保证每个子序列有序,最终,就可以得到一个有序的结果了。我们用图来说明:
···图片正在加载···
images/mergeSort/proc.png
归并排序流程
在图的上半部分,一个序列被一直拆,直到拆不下去(序列长度为1),之所以拆分到长度为1的序列,是因为任何一个长度为1的序列都是有序的——它们本身就不需要排序,这点很容易想到。注意,在拆分过程中,数的顺序始终都没有变化。很显然,这是一个递归过程。偶数情况如图上所示,考虑奇数情况:5 -> 2, 3 -> 1, 1, 1, 2 -> 1, 1, 1, 1, 1,依然是细分到了长度为1。这样的话,对于一个数组buff,我们就可以实现一下拆分过程:
void mergeSort_split(int *buff, int l, int r)
{
    int  mid;
    if (l == r)                                 // 已经分解到1个元素那么大了
        return;
    mid = l + (r - l) / 2;                      // 找到这个子序列的"中间位置"
    mergeSort_split(buff, l, mid);              // 递归分解
    mergeSort_split(buff, mid + 1, r);
}
注意,l, r是作为buff数组下标而输入的,因此,我们应当判断两个下标相等——这样就表明这个子序列的长度为1了。同时,我们需要保证子序列之间不会发生重叠,因此上一个是在[l, mid],另一半就是[mid + 1, r]。在下图中,我加上了数组下标,可以更好的理解上述程序。
small
下半部分则是理拆分的序列,把它们合并——针对于只有一个元素的序列,它们自然是有序的,而多个元素的序列,也要保证它们有序。注意到,在合并过程中,每个序列总是被从小到大(当然,也可以从大到小)的来合并。从1个元素的有序序列合并,我们得到了4个2个元素的有序序列,之后合并2个元素的有序序列,我们得到2个4个元素的有序序列,最后把它们合并,得到1个8个元素的有序序列,也就是结果。这个过程中自始自终强调了合并有序序列,因此,如何合并也是个问题。我们考虑一个简单的合并,输入的两个序列都是有序的,可以看到它们的元素都是从小到大的结果。
small
首先,我们准备两个数组下标,它们分别指向左边的序列和右边的序列。准备一个新的数组,用于存放输出的结果。
small
然后同时考虑两边的子序列,从其中选出较小(当然,你要从大到小就是选择较大的)的那一个,放入输出缓冲区,同时输出的偏移位置增加1。在上图中,pleft和pright所在位置元素最小的是pleft,也就是2。因此得到下面的结果:
small
继续比较,发现pleft和pright里面小的一个是pright,也就是4,得到下面结果:
small
继续比较,发现pright比pleft小,因此将pright送入缓冲区,得到下面结果:
small
很显然,右边的子序列已经读取完成,此时我们不再比较。但问题左边的子序列还有元素——因此,我们把剩下的元素全部移入缓冲区。由于要么是左边的子序列有元素,要么是右边的序列有元素,因此我们可以省去判断哪边序列有元素这个问题,直接将还有未处理元素的序列中的未处理元素全部送入缓冲区数组即可。至此,我们得到下列结果。
small
而最终的缓冲区就是已经合并的子序列,将它复制到原先的数组中去,作为下一次被合并的子序列或者说是操作数。对每两个子序列进行这个操作,最终即可得到一个结果。这样,整个归并排序就完成了。考虑代码实现,我们需要在之前的那个拆分过程后面添加上归并代码。也就是这样的:
// 归并排序(子序列合并)
void __merge(int *buff, int l, int mid, int r)
{
    int  *temp = (int*)alloca((r - l + 1) * sizeof(int));
    int  *t, p1, p2;                            // p1, p2是左右两个序列的下标
    int  *arrbeg;
    t = temp;
    p1 = l;
    p2 = mid + 1;
    while (p1 <= mid && p2 <= r)                // 这个循环负责同时遍历两个子序列
    {                                           // 把小的那个放入数组, 然后移动temp下标
        *t++ = buff[p1] < buff[p2] ? buff[p1++] : buff[p2++];
    }
    while (p1 <= mid)                           // 最终, 要么是p1也就是左边部分没有完, 要么是p2右边部分没有完成
        *t++ = buff[p1++];                      // 两个循环会有一个执行, 把剩下的数据送进去
    while (p2 <= r)
        *t++ = buff[p2++];
    arrbeg = buff + l;                          // 子序列开始的位置
    while (temp < t)                            // 复制数据
    {
        *arrbeg++ = *temp++;                    // temp为栈帧内分配, 之后不再需要
    }
}
// 归并排序
void mergeSort(int *buff, int l, int r)
{
    int  mid;
    if (l == r)                                 // 已经分解到1个元素那么大了
        return;
    mid = l + (r - l) / 2;                      // 找到这个子序列的"中间位置"
    mergeSort(buff, l, mid);                    // 递归分解
    mergeSort(buff, mid + 1, r);
    __merge(buff, l, mid, r);                   // 并
}
注意实现过程中的每个数组的范围,一定要防止越界。mergeSort函数的参数l, r是数组下标,因此我们需要排序一个长度为8的buff,应该这样写:mergeSort(buff, 0, 8 - 1),原因是数组下标以0开始,因此是8-1而不是8。