排序算法之归并排序-蒲公英云

排序算法之归并排序

先看一下下面这张图

Center

下面分析归并排序：

归并排序把数组划分成几个小数组，然后小数组成划分，直到每个数组都只有一个元素，然后将相邻的两个数组进行合并，再将合并后的数组继续合并，直到合并成一个数组。总体的思想是先拆分再合并。

归并排序的时间复杂度为O(nlogn)。

由于合并的时候需要额外的一个数组来保存，因此空间复杂度为O(n)。

归并排序合并的时候是相邻的数组进行合并，因此是稳定的。

归并排序可用递归实现，先递归将数组拆分，拆到最小时返回，然后将拆分的两个数组进行合并。

C++代码

/*
* 归并排序
* 先将数组拆分成小数组，然后在合并成大数组
* 合并的时候进行排序，使用一个辅助的空间来存储排好序的元素
* O(nlogn)
* O(n)
* 稳定
*/
#define RECURSION 0
template <typename T>
void SortHelp<T>::mergeSort(T l[], int length) {
#ifdef RECURSION
    //使用递归
    merge(l, 0, length - 1);
#else
#endif // RECURSION
}
template<typename T>
void SortHelp<T>::merge(T l[], int start, int end)
{
    //数组只剩下一个元素
    if (start == end)
    {
        return;
    }
    int mid = (start + end) / 2;
    merge(l, start, mid);
    merge(l, mid + 1, end);
    //合并两个数组
    T* temp = (T*)malloc(sizeof(T)*(end - start + 1));
    int i, j, k;
    for (i = start, j = mid + 1, k = 0; i <= mid && j <= end; k++)
    {
        if (l[i] < l[j])
        {
            temp[k] = l[i];
            i++;
        }
        else
        {
            temp[k] = l[j];
            j++;
        }
    }
    while (i <= mid)
    {
        temp[k++] = l[i++];
    }
    while (j <= end)
    {
        temp[k++] = l[j++];
    }
    //复制回原数组
    for (i = start, k = 0; i <= end; i++)
    {
        l[i] = temp[k++];
    }
}

也可以不使用递归，不用拆分，直接从最小单位开始合并，合并完一趟后把合并单位翻倍。

C++代码

/*
* 归并排序
* 先将数组拆分成小数组，然后在合并成大数组
* 合并的时候进行排序，使用一个辅助的空间来存储排好序的元素
* O(nlogn)
* O(n)
* 稳定
*/
//#define RECURSION 0
template <typename T>
void SortHelp<T>::mergeSort(T l[], int length) {
#ifdef RECURSION
    //使用递归
    merge(l, 0, length - 1);
#else
    //不使用递归
    int dt = 1;
    T* temp = (T*)malloc(sizeof(T)*length);
    int i, j, k;
    while (dt < length)
    {
        for (int s = 0; s < length; s += 2 * dt)
        {
            //合并数组[s,s+dt-1]和数组[s+dt,s+2dt-1]
            for (i = s, j = s + dt, k = 0; i < s + dt && j < s + 2 * dt && j < length; k++)
            {
                if (l[i] < l[j])
                {
                    temp[k] = l[i++];
                }
                else
                {
                    temp[k] = l[j++];
                }
            }
            while (i < s + dt)
            {
                temp[k++] = l[i++];
            }
            while (j < s + 2 * dt && j < length)
            {
                temp[k++] = l[j++];
            }
            //复制回源数组
            for (i = s, k = 0; i < s + 2 * dt && i < length; i++, k++)
            {
                l[i] = temp[k];
            }
        }
        dt *= 2;
    }
    free(temp);
#endif // RECURSION
}