归并排序

归并排序是一种经典的排序算法，属于分治算法的一种。其核心思想是将一个大问题分解成若干个较小的子问题来解决，然后根据子问题的解构建原问题的解。在排序问题中，归并排序将数组分成两半，分别对这两半进行排序，然后将排序好的两个半部分合并成一个有序的整体。

归并排序的具体步骤如下：
分解：将待排序的数组分成两部分，直到每部分只有一个元素或为空。如果数组只有一个元素或为空，则它自然是有序的。

解决：递归地对每部分进行归并排序。

合并：将排序好的两部分合并成一个有序的整体。

归并排序的算法流程可以用以下伪代码表示：

function mergeSort(array)
    if length of array <= 1
        return array
    else
        middle = length of array / 2
        left = mergeSort(first half of array)
        right = mergeSort(second half of array)
        return merge(left, right)

function merge(left, right)
    result = empty array
    while left is not empty and right is not empty
        if the first element of left <= the first element of right
            add the first element of left to result
            remove the first element from left
        else
            add the first element of right to result
            remove the first element from right
    end while
    add the remaining elements of left to result
    add the remaining elements of right to result
    return result

算法流程如下：
调用归并排序：调用mergeSort函数，传入数组和索引0（数组起始）和n - 1（数组结束）。

递归分解：mergeSort函数首先计算中间索引middle，然后对数组的左半部分和右半部分分别进行递归调用。

基线条件：当数组的大小小于等于1时，递归结束，因为单个元素或空数组自然是有序的。

合并：在递归调用返回后，mergeSort函数调用merge函数，传入数组和左右两部分的索引。

合并过程：
merge函数创建两个临时数组temp1和temp2，分别存储原数组的左右两部分。
使用两个索引i和j分别遍历temp1和temp2，比较元素大小，并将较小的元素放入原数组的相应位置。
当一个临时数组的所有元素都被合并后，将另一个数组的剩余元素拷贝到原数组中。

归并排序是一种稳定的排序算法，因为它可以保持相等元素的原始顺序。不过，由于它需要额外的空间来存储临时数组，因此它的空间复杂度为O(n)。时间复杂度为O(nlogn)。

具体代码如下：

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& arr, int left, int middle, int right) {
    // 创建两个临时数组用于存储分割后的数组
    int n1 = middle - left + 1;  // 左边数组的大小
    int n2 = right - middle;     // 右边数组的大小
    vector<int> temp1(n1);
    vector<int> temp2(n2);

    // 分别将原数组中的元素拷贝到临时数组中
    for (int i = 0; i < n1; i++) {
        temp1[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        temp2[j] = arr[middle + 1 + j];
    }

    // 合并两个临时数组到原数组中
    int i = 0;  // 左边数组的起始索引
    int j = 0;  // 右边数组的起始索引
    int k = left; // 合并后数组的起始索引

    while (i < n1 && j < n2) {
        if (temp1[i] <= temp2[j]) {
            arr[k] = temp1[i];
            i++;
        } else {
            arr[k] = temp2[j];
            j++;
        }
        k++;
    }

    // 将剩余的元素拷贝到原数组中
    while (i < n1) {
        arr[k] = temp1[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = temp2[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        // 分割数组并递归调用归并排序
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        // 合并两个有序数组
        merge(arr, left, middle, right);
    }
}

int main() {
    vector<int> arr = {9, 5, 7, 3, 1, 8, 6, 2, 4};
    int n = arr.size();

    cout << "原始数组: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 调用归并排序算法
    mergeSort(arr, 0, n - 1);

    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}