31 归并排序.md

#数据结构 #算法 #C

[84] 归并排序(Merge Sort)

1. 算法思想

将多个已经有序的序列合并成一整个有序序列。

2. 算法过程

对比i，j所指元素，选择一个更小的放入到k所指的位置（使用双指针法）。

当只剩下一个子表未合并的时候，可以将该表剩下升序的其他元素全部加到总表之中。 核心操作：把数组当中内部的两个有序序列归并成一个。

3. 算法实现

// 辅助数组B
int* B = (int *)malloc(n * sizeof(int));

// A[low, mid] 和 A[mid+1, high] 各自有序，将两个部分归并
void Merge (int A[], int low, int mid, int high){
    int i, j, k;
    for (k= low; k<=high; k++){
        B[k] = A[k];
    }
    // 将A中所有的元素复制到B中
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++){
        if (B[i] <= B[j]){
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while (i <= mid){
        A[k++] = B[i++];
    }
    while (j <= high){
        A[k++] = B[i++];
    }
}

void MergeSort(int A[], int low, int high){
    if (low < high){
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid + 1, high);
        MergeSort(A, low, mid, high);
    }
}