数据结构_排序⑥归并排序

2019-08-15 0 条评论 54 次阅读 0 人点赞

归并排序

归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
时间: N * logN
空间: N + logN ~ N
稳定性: 稳定

void _MergeSort(int*a, int left, int right, int* tmp){
    //区间只剩一个元素, 不需要分解和归并
    if(left >= right)
        return;
    //分解
    int mid = left + (right - left) / 2;
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);

    //归并 [left, mid] , [mid + 1, right]
    int begin1 = left, end1 = mid,
            begin2 = mid + 1, end2 = right;  //begin1 ~ end2 --> left ~ right
    int tmpindex = begin1;
    while (begin1 <= end1 && begin2 <= end2){
        // < 不稳定   <= 稳定
        if (a[begin1] <= a[begin2]){
            tmp[tmpindex++] = a[begin1++];
        }else{
            tmp[tmpindex++] = a[begin2++];
        }
    }
    while (begin1 <= end1){
        tmp[tmpindex++] = a[begin1++];
    }
    while (begin2 <= end2){
        tmp[tmpindex++] = a[begin2++];
    }
    //拷贝到原有数组的对应区间
    memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}

void MergeSort(int* a, int n){
    int* tmp = (int*)malloc(sizeof(int));
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
    tmp = NULL;
}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)