算法踩坑5-归并排序

背景

接上面四篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
算法踩坑3-堆排序
算法踩坑4-冒泡排序

来继续聊聊最近我写的一些算法的小例程，这次要聊的是归并排序，是一个时间复杂度O(NLogN)的算法。归并排序是经典的递归的案例。

主要从以下几方面来说的：

• 归并排序思想
• 归并排序实现
• 归并排序优化
• 时间分析

归并排序思想

归并排序是经典的分治算法的经典实现，把一个大的问题逐步的分解为两部分，然后再进行重组，最终得到一个完整的结果。归并排序有两个重要的步骤是拆分和重组。

归并重组

先说下归并排序的重组思路，前提条件是两个已经排序好的子数组，比如数组A和数组B。
各自有一个指针指向A和B，比如aPtr和bPtr。
使用aPtr和bPtr和遍历数组A和数组B，比较aPtr和bPtr指向的元素，把小的那个元素复制到临时数组，直到aPtr或者bPtr到达数组A或者数组B的末尾，然后把A或者数组B的末尾中没有拷贝到临时数组中的其他元素拷贝到临时数组中去。此时，临时数组是一个合并之后的有序的数组，这个是归并重组的过程。

归并拆分

归并的拆分是为了归并重组服务的，递归的把问题拆解为两部分，最后的递归出口是只有一个元素的情况，那么数组A和数组B是只有一个元素的数组，此时进行归并重组，重组之后的两个元素的数组是有序的，然后需要把临时数组中有序的序列复制到原数组中，后面归并重组步骤需要使用到前面已经排序的结果。

归并排序实现

void MSort(ElementType arr[], ElementType tmpArr[], int left, int right) {
    int Center;
    if (left < right) {
        Center = (left + right) / 2;
        
        MSort(arr, tmpArr, left, Center);
        MSort(arr, tmpArr, Center+1, right);
        // [left, center]、[center+1, right] 这两部分是排好序的了，合并这两部分
        Merge(arr, tmpArr, left, Center+1, right);
    }
}

void MergeSort(ElementType arr[], int count) {
    ElementType *tmpArr = malloc(count * sizeof(ElementType));
    MSort(arr, tmpArr, 0, count-1);
}

void Merge(ElementType arr[], ElementType tmpArr[], int lPos, int rPos, int rightEnd) {
    int i, leftEnd, tmpPos, count;
    leftEnd = rPos - 1;
    tmpPos = lPos;
    count = rightEnd - lPos + 1;
    // 比较元素复制到临时数组中,！！注意需要使用<=符号
    while (lPos <= leftEnd && rPos <= rightEnd) {
        if (arr[lPos] < arr[rPos]) {
            tmpArr[tmpPos++] = arr[lPos++];
        } else {
            tmpArr[tmpPos++] = arr[rPos++];
        }
    }
    // 拷贝剩余的元素到临时数组中！！注意需要使用<=符号
    while (lPos <= leftEnd) {
        tmpArr[tmpPos++] = arr[lPos++];
    }
    while (rPos <= rightEnd) {
        tmpArr[tmpPos++] = arr[rPos++];
    }
    
    // 把排序的元素复制到原来的数组中
    for (i = 0; i<count; i++, rightEnd--) {
        arr[rightEnd] = tmpArr[rightEnd];
    }
}

归并排序优化

归并排序以O(NLogN)最坏的情形运行时间运行，使用的比较次数几乎是最优的。

时间分析

归并排序的时间分析和快速排序的时间分析是一样的，一次排序的时间为两次分割的时间加上遍历这次元素所花费的时间：T(N) = 2T(N/2) + N，使用叠缩求和，最终可以得到时间复杂度的结果，该结果是最坏情况的结果。

T(N) = 2T(N/2) + N
T(N/2) =2 T(N/4) + N
T(N/4) = 2T(N/8) + N
=>
T(N)/N = T(N/2)/N/2 + 1
T(N/2)/(N/2) = T(N/4)/(N/4) +1
T(N/4)(N/8) = T(N/8)/(N/16) +1
...
T(N)/N = T(1)/1 + logN
T(N) = NlogN

One More Thing

噢！我是算法，点我