老青菜

归并排序

2019-05-14

归并排序(MergeSort)是建立在归并操作上的一种有效的排序算法,也称合并排序。
和快排类似,采用分治法(Divide and Conquer)将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并。

算法思路

  1. 把长度为n的输入序列分成两个长度为n/2的子序列。
  2. 对这两个子序列分别采用归并排序,直到子序列长度为1
  3. 将两个排序好的子序列合并成一个最终的排序序列。

代码实现

/// 归并排序
void mergeSort(int *array, int length) {
    int *newArray = mergeSortRecursive(array, length, 0, length-1);
    for (int i=0; i<length; i++) {
        printf("%d,",newArray[i]);
    }
    printf("\r\n");
    free(newArray);
}
/// 递归执行划分、合并操作
int* mergeSortRecursive(int *array, int length, int left, int right) {
    int *newArray = (int *)malloc((right-left+1)*sizeof(int));
    memset(newArray, 0, sizeof(int)*(right-left+1));
    if (left >= right) {
        newArray[0] = array[left];
        return newArray;
    }
    int leftEnd = left+(right-left)/2;
    int rightStart = leftEnd+1;
    // 划分左右区间
    int *leftArray = mergeSortRecursive(array, length, left, leftEnd);
    int *rightArray = mergeSortRecursive(array, length, rightStart, right);
    // 合并左右区间
    mergeHandle(newArray, leftArray, leftEnd-left+1, rightArray, right-rightStart+1);
    free(leftArray);
    free(rightArray);
    return newArray;
}
/// 合并左右两侧区域
void mergeHandle(int *newArray, int *leftArray, int leftLength, int *rightArray, int rightLength) {
    int leftIndex = 0;
    int rightIndex = 0;
    int index = 0;
    while (true) {
        // 双指针,对比左右区域
        int leftItem = leftArray[leftIndex];
        int rightItem = rightArray[rightIndex];
        if (leftItem <= rightItem) {
            // left <= right
            newArray[index] = leftItem;
            index++;
            leftIndex++;
        }
        else {
            // right < left
            newArray[index] = rightItem;
            index++;
            rightIndex++;
        }
        // 左侧区域或右侧区域已经遍历完
        if (leftIndex >= leftLength || rightIndex >= rightLength) break;
    }
    // 左侧区域有剩余元素
    if (leftIndex<leftLength) {
        for (int i=leftIndex; i<leftLength; i++) {
            newArray[index] = leftArray[i];
            index++;
        }
    }
    // 右侧区域有剩余元素
    if (rightIndex<rightLength) {
        for (int i=rightIndex; i<rightLength; i++) {
            newArray[index] = rightArray[i];
            index++;
        }
    }
}

算法分析

归并排序是一种稳定的排序方法。性能不受输入数据的影响,比选择排序要稳定。
时间复杂度:始终都是O(nlogn)
空间复杂度:O(n)

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章