分治算法简介——归并排序

Author: 2015-08-23

ACM

, , ,

　　归并排序应用分治算法，具有O(nlogn)的时间复杂度，其工作流程可以概述为：

  1. 将长度为n的无序序列分割成n个子序列，每个序列包含1个元素；
  2. 重复将子序列相互合并称为有序序列，直到只剩下1个序列，即为排序后的序列。

　　一个例程如下所示：

void merge(int array[], int tmpArray[], int lPos, int rPos, int rEnd) {
    int i, lEnd, num, tmpPos;
    
    lEnd = rPos - 1;
    tmpPos = lPos;
    num = rEnd - lPos + 1;
    
    while (lPos <= lEnd && rPos <= rEnd) {
        if (array[lPos] <= array[rPos])
            tmpArray[tmpPos++] = array[lPos++];
        else
            tmpArray[tmpPos++] = array[rPos++];
    }
    
    while (lPos <= lEnd)
        tmpArray[tmpPos++] = array[lPos++];
    
    while (rPos <= rEnd)
        tmpArray[tmpPos++] = array[rPos++];
    
    for (i = 0; i < num; ++i, rEnd--) {
        array[rEnd] = tmpArray[rEnd];
    }
    
}

void mSort(int array[], int tmpArray[], int left, int right) {
    int center;
    
    if (left < right) {
        center = (left + right) / 2;
        mSort(array, tmpArray, left, center);
        mSort(array, tmpArray, center + 1, right);
        merge(array, tmpArray, left, center + 1, right);
        
    }
}

void mergeSort(int array[], int n) {
    int *tmpArray;
    
    tmpArray = (int *)malloc(n * sizeof(int));
    if (tmpArray != NULL) {
        mSort(array, tmpArray, 0, n - 1);
        free(tmpArray);
    } else {
        printf("No space for tmp array!\n");
    }
}

在mergeSort() 中，分配了一个临时数组tmpArray 用于保存中间数据，然后对0到n-1区间的待排序数组进行mSort() 。mSort() 按照left和right为起始位置，将待排序数组等分为两份，递归地对两份数组再次调用mSort() 排序，最后通过merge() 将两个已排序的数据合并为一个。merge() 将输入的两个已排序数据合并为一个，合并的结果先放在tmpArray 里面，合并完成后再由tmpArray 复制回array 。注意这里只在mergeSort() 中分配了一个临时数组，并在merge() 中重复利用，避免了频繁分配空间导致的性能下降。