归并排序c++代码

归并排序是一种经典的分治算法，它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后合并两个有序子数组，最终得到整个数组有序。

cpp
#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组存放左右两部分的元素
    std::vector<int> leftArr(n1);
    std::vector<int> rightArr(n2);

    // 拷贝数据到临时数组 leftArr[] 和 rightArr[]
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    // 归并临时数组到 arr[left..right]
    int i = 0;
    int j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将左边剩余元素复制到 arr 中
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // 将右边剩余元素复制到 arr 中
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;

        // 递归地对左右两部分进行排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的两部分
        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    // 调用归并排序函数
    mergeSort(arr, 0, arr.size() - 1);

    std::cout << "\nSorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}

这个程序首先定义了一个merge函数，用于合并两个有序数组。然后定义了mergeSort函数，它采用递归方式对数组进行归并排序。最后，在main函数中演示了如何使用这两个函数进行排序。

merge函数：这个函数用于合并两个有序数组。它首先计算左右两个子数组的大小，然后创建两个临时数组leftArr和rightArr，分别用于存放左右两个子数组的元素。接下来，通过比较左右两个子数组的元素，将较小的元素依次放入原始数组arr中，直到其中一个子数组被遍历完。最后，将剩余的元素从左右两个子数组复制到原始数组中。

mergeSort函数：这个函数是归并排序的核心，采用递归方式对数组进行排序。它首先检查数组的大小，如果数组大小大于1，则进行计算中间位置mid。递归地对数组的左半部分进行排序。递归地对数组的右半部分进行排序。调用merge函数合并已排序的左右两部分。

main函数：在main函数中，创建了一个示例数组arr，然后输出原始数组的内容。接着，调用mergeSort函数对数组进行排序，并输出排序后的结果。