C++归并排序算法详解

什么是归并排序

归并排序是一种基于“分治思想”的排序算法，它将待排序的数组不断分割成若干个子数组，直到每个子数组中只有一个元素。然后将那些只有一个元素的子数组归并成两个元素有序的子数组；接着将两个元素有序的子数组再次归并成四个元素有序的子数组；依次类推，直到归并为一个完整的排序数组。

归并排序的流程

1.分解：将待排序的数组从中间分割成两个子数组，直到每个子数组中只有一个元素

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

2.合并：将两个有序的子数组合并为一个有序的数组

void merge(int array[], int left, int middle, int right) {
    int i = left, j = middle + 1, k = 0;
    int temp[right - left + 1];
    while(i <= middle && j <= right) {
        if(array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while(i <= middle) {
        temp[k++] = array[i++];
    }
    while(j <= right) {
        temp[k++] = array[j++];
    }
    for(int l = 0; l < k; l++) {
        array[left + l] = temp[l];
    }
}

归并排序的时间复杂度

归并排序的时间复杂度为O(nlogn)。其中n是数组的长度。因为每次将数组分成两个子数组，并将每个子数组合并，所以总共有logn次合并，每次合并的时间复杂度是O(n)。

示例

下面是一个使用归并排序对数组进行排序的例子：

#include <iostream>
using namespace std;

void merge(int array[], int left, int middle, int right) {
    //合并两个有序的子数组
}

void mergeSort(int array[], int left, int right) {
    //分解数组并合并
}

int main() {
    int array[] = {5, 2, 4, 6, 1, 3};
    int length = sizeof(array) / sizeof(*array);
    mergeSort(array, 0, length - 1);
    for(int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}

上述例子中，我们将一个无序的数组{5, 2, 4, 6, 1, 3}使用归并排序进行排序。最终的输出结果为1 2 3 4 5 6。