归并排序


思想

归并排序（merge sort）是建立在归并操作上的一种有效的排序算法,它以 O(nlogn) 最坏情形运行时间运行。它是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序可并行实现。

归并排序示例图如下：

实现

合并操作

基本的合并算法是取两个输入数组 A 和 B、一个输出数组 C，以及三个计数器 Aptr， Bptr， Cptr。它们初始置于对应数组的开始端。A[Aptr]和 B[Bptr]中的较小者被拷贝到 C 中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余部分拷贝到 C 中。

如果对 Merge 的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有 log N 个临时数组处在活动期，这对于小内存机器是致命的。另一方面，如果 Merge 例程动态分配并释放最小量临时内存，那么由 malloc 占用的时间会很多。因此，可将输入数组分成两个输入数组。

/***    @description 对数组a的 a[leftPos, rightPos - 1] 和 a[rightPos, rightEnd] 两部分进行合并操作，结果暂存到tmpArray中，最后拷贝回数组a。
*/
void Merge(ElementType a[], ElementType tmpArray[], int leftPos, int rightPos, int rightEnd)
{
    int i, leftEnd, numOfElements, tmpPos;
 
    leftEnd = rightPos - 1;
    tmpPos = leftPos;
    numOfElements = rightEnd - leftPos + 1;       
 
    //main loop
    while (leftPos <= leftEnd && rightPos <= rightEnd)
        if (a[leftPos] < a[rightPos])
            tmpArray[tmpPos++] = a[leftPos++];
        else
            tmpArray[tmpPos++] = a[rightPos++];
 
    //get rest of first half
    while (leftPos <= leftEnd)
        tmpArray[tmpPos++] = a[leftPos++];
 
    //get rest of second half
    while (rightPos <= rightEnd)
        tmpArray[tmpPos++] = a[rightPos++];
 
    //copy tmpArray back
    for (i = 0; i < numOfElements; ++i, rightEnd--)
        a[rightEnd] = tmpArray[rightEnd];
}

归并排序

/***    @description 归并排序主算法，对数组a[left, right] 进行归并排序，使用到了暂存数组tmpArray。
*/
void MSort(ElementType a[], ElementType tmpArray[], int left, int right)
{
    int center;
 
    if (left < right)
    {
        center = (left + right) / 2;
        MSort(a, tmpArray, left, center);
        MSort(a, tmpArray, center + 1, right);
        Merge(a, tmpArray, left, center + 1, right);
    }
}

算法主体

/***    @description 归并排序算法，封装了开辟临时存储空间的操作。
*/
void MergeSort(ElementType a[], int n)
{
    ElementType *tmpArray;
 
    tmpArray = (ElementType *)malloc(sizeof(ElementType) * n);
    if (tmpArray != NULL)
    {
        MSort(a, tmpArray, 0, n - 1);
        free(tmpArray);
    }
    else
        puts("No space of tmp Array!");
}

本文永久更新链接地址：

相关内容