acwing归并排序
时间: 2023-10-12 20:05:47 浏览: 45
归并排序是一种经典的排序算法,它采用了分治的思想。下面是acwing平台上给出的归并排序的示例代码:
```cpp
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}
```
这段代码使用了递归的方式实现了归并排序。首先,它将待排序的数组不断二分,直到每个子数组只剩下一个元素。然后,将这些子数组进行合并,合并的过程中将较小的元素放在临时数组中,最后再将临时数组中的元素复制回原数组。通过不断递归和合并,最终实现整个数组的排序。
这段代码的时间复杂度为O(nlogn),其中n表示数组的长度。归并排序是一种稳定的排序算法,适用于各种数据规模的排序任务。希望对你有所帮助!如果有其他问题,欢迎继续提问。