常见排序算法(5)--归并排序(递归版)

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

"治" 代码实现

图看完了，现在来看代码吧。

void merge(int *arr, int left, int mid, int right ,int *temp)
{
    int i = left;//左序列指针
    int j = mid+1;//右序列指针
    int t = 0;//临时数组指针

    while (( i <= mid) && ( j <= right))
    {
        if (arr[i] < arr[j])
        {
            temp[t++] = arr[i++];
        }
        else
        {
            temp[t++] = arr[j++];
        }
    }
    while (i <= mid)//将左边剩余元素填充进temp中
    {
        temp[t++] = arr[i++];
    }
    while (j <= right)//将右序列剩余元素填充进temp中
    {
        temp[t++] = arr[j++];
    }
    t = 0;
    //将temp中的元素全部拷贝到原数组中
    while (left <= right)
    {
        arr[left++] = temp[t++];
    }
}

这个函数有点难理解，我们还是拿上图的具体例子来说吧。执行merge(arr, 0, 4, 8, temp)，其实就是把{4,5,7,8}(暂时称为左子数组)和{1,2,3,6}(右子数组)两个已经有序的子序列，合并为最终序列{1,2,3,4,5,6,7,8}。先比较左右子数组的第一个元素的大小，把较小的存到临时数组的第一个元素，然后把对应的子数组的指针加1，继续比较。直到左右子数组中某一个子数组完全被复制到了temp中，接下来的while循环做的事情就是把剩下的子数组中的剩余元素都复制进temp。由于不知道是左子数组还是右子数组剩余元素，所以都要写一遍。最后把temp数组的元素拷贝到arr中，arr就排序好了。

"分" 代码实现

void MSort(int *arr, int left, int right, int *temp)
{
    // if (left = right) return; 
    if (left < right)
    {
        int mid = (left + right) / 2;
        MSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
        MSort(arr, mid+1, right, temp);//右边归并排序，使得右子序列有序
        merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
    }
}

"分"采用了递归的方法，采用了折半的策略，先归并左子数组，再归并右子数组，再把左右子数组合并。有的读者可能觉得MSort函数没有终止条件，其实它是有的，隐含的条件是这个if (left = right) return;，因为当left = right时，其实只有一个元素，肯定是有序的。

归并排序递归版 代码实现

// 归并排序递归版
void MergeSort(int *arr, int length)
{
    int *temp = (int *)malloc(sizeof(int) * length);//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    MSort(arr, 0, length-1, temp);
    free(temp);
}

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。