编写一个时间复杂度O(nlogn)的程序c++

在C++中编写一个时间复杂度为O(nlogn)的程序通常是涉及到一些算法操作，比如排序、查找等，这里以快速排序为例，它是一种常用的分治策略算法，其平均和最好情况下的时间复杂度就是O(nlogn)：

#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high); // 分割元素
        quickSort(arr, low, pivot - 1);       // 对左半部分递归排序
        quickSort(arr, pivot + 1, high);      // 对右半部分递归排序
    }
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];   // 选择最后一个元素作为基准
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);   // 将小于基准的元素交换到左边
        }
    }
    std::swap(arr[i + 1], arr[high]); // 将基准放到正确的位置
    return i + 1;
}

int main() {
    std::vector<int> nums = {9, 7, 5, 11, 12, 2, 14, 3};
    int n = nums.size();
    quickSort(nums, 0, n - 1);
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

在这个例子中，`quickSort`函数是一个递归函数，而`partition`函数则是分割的过程，整体的时间复杂度符合O(nlogn)。