请帮我用c++写一段时间复杂度O(nlogn)的排序算法

### 回答1：

#include <stdio.h>
int merge(int arr[], int l, int m, int h)
{
int n1 = m - l + 1;
int n2 = h - m;

int L[n1], R[n2];

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

int i = 0;
int j = 0;
int k = l;

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

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

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

void mergeSort(int arr[], int l, int h)
{
if (l < h) {
int m = (l + h) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, h);

merge(arr, l, m, h);
}
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

return 0;
} 答案：我可以为您提供一段C语言的时间复杂度为O(nlogn)的排序算法：

### 回答2：
在C语言中，可以使用快速排序算法来实现时间复杂度为O(nlogn)的排序算法。具体实现如下：

#include <stdio.h>

// 快速排序核心函数
void quicksort(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(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择基准元素
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i+1], &arr[high]);
    return i+1;
}

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组：");
    printArray(arr, size);

    quicksort(arr, 0, size-1);

    printf("排序后的数组：");
    printArray(arr, size);

    return 0;
}

上述代码实现了快速排序算法，通过递归调用quicksort函数实现对数组的分割和排序，并通过partition函数将数组划分为两个子数组。最后，使用swap函数实现元素值的交换，从而实现排序。最后在主函数中，调用quicksort函数对数组进行排序，并打印排序后的结果。

快速排序算法的时间复杂度为O(nlogn)，在平均情况下具有较高的效率，是常用的排序算法之一。

### 回答3：
可以用归并排序来实现时间复杂度O(nlogn)的排序算法。

归并排序是基于分治法的排序算法，它将待排序的数组不断地二分为更小的子数组，直到子数组只有一个元素。然后将这些子数组两两合并，按照大小顺序合并成一个更大的有序数组。重复这个步骤，直到最后合并为一个有序数组。

具体实现归并排序的C代码如下：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
 
    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;
    int j = 0;
    int k = left;
 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(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);
    }
}

对于一个长度为n的数组，mergeSort(arr, 0, n-1)即可调用归并排序。归并排序的时间复杂度为O(nlogn)。