c++实现归并排序,并给出其时间复杂性
时间: 2024-10-16 10:12:52 浏览: 4
归并排序是一种分治算法,它将数组分成两个子数组,对每个子数组递归地进行排序,然后合并已排序的子数组。以下是C++实现归并排序的一个基本示例:
```cpp
#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];
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(std::vector<int>& arr, int left, int right) {
if (left >= right) return; // 如果只有一个元素或为空,直接返回
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 = {9, 7, 5, 11, 12, 2, 14, 3};
int n = arr.size();
mergeSort(arr, 0, n - 1);
for (auto num : arr) {
std::cout << num << " ";
}
return 0;
}
```
归并排序的时间复杂度为O(n log n),其中n是数组的长度。这是因为无论数组大小如何,都需要进行log n次递归分割(分治阶段),而在合并过程中,每次需要遍历两个已排序的子数组,时间复杂度是线性的,即O(n)。因此,总的时间复杂性是O(n log n)。
阅读全文