算法思想

归并排序是分治法的典型应用。它通过将已有的子序列合并,来得到有序的完整序列。如果是两个有序表合并为一个有序表,称之为2-路归并。

算法特点

性能稳定,与选择排序类似,归并排序并不受输入数据的影响,但性能优于前者,其时间复杂度为O(n*logn),但空间复杂度较高,因为在排序过程中需要额外的内存空间。

算法步骤

  1. 将长度为N的序列分成两个长度为N/2的子序列;
  2. 对子序列重复进行步骤1的划分,直到不能分割为止;
  3. 对以上子序列进行两两归并,直到合并成一个有序的序列。

CPP代码

// 归并排序(Merge Sort)
void MergeSort(int arr[], int size) {
    if (size < 2)
        return;

    int mid = size / 2;
    int *L = new int[mid];
    int *R = new int[size - mid];

    for (int i = 0; i < mid; ++i)
        L[i] = arr[i];
    for (int j = mid; j < size; ++j)
        R[j - mid] = arr[j];

    MergeSort(L, mid);
    MergeSort(R, size - mid);
    Merge(arr, L, mid, R, size - mid);

    delete[]R;
    delete[]L;
}

void Merge(int arr[], const int *L, int leftCount, const int *R, int rightCount) {
    int i = 0, j = 0, k = 0;

    while (i < leftCount && j < rightCount) {
        if (L[i] < R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    while (i < leftCount)
        arr[k++] = L[i++];

    while (j < rightCount)
        arr[k++] = R[j++];
}

最后修改日期:2020年10月11日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。