c++输入数组并用分治法递增排序

在C++中，可以使用分治法（如快速排序、归并排序等）对数组进行递增排序。这里以归并排序为例，它是一种稳定的排序算法，适合处理大规模数据。下面是基本步骤：

首先，引入必要的头文件，并定义一个归并排序函数：

#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> L(n1), R(n2);

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    // 将剩余未比较元素复制到数组arr
    while (i < n1)
        arr[k++] = L[i++];

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

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> inputArray = {9, 7, 5, 11, 12, 2, 14, 3};
    int arraySize = inputArray.size();

    std::cout << "Original Array: ";
    for (const auto& num : inputArray)
        std::cout << num << " ";

    mergeSort(inputArray, 0, arraySize - 1);

    std::cout << "\nSorted Array: ";
    for (const auto& num : inputArray)
        std::cout << num << " ";

    return 0;
}

运行上述代码后，`inputArray`将按照递增顺序排列。