c++ 给定数组:A[8] = {16,25,5,8,13,1,10,3}。排序代码截图一定要清晰。 (1)使用归并排序实现对数组A的升序排列
时间: 2024-11-22 15:36:08 浏览: 1
判定给定数组是否已排序
归并排序是一种分治算法,它将一个数组分为两半,分别递归地排序,然后合并这两个已排序的部分。对于给定的 C++ 代码,这里是一个使用归并排序的例子来对整数数组 `A` 进行升序排序:
```cpp
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
std::vector<int> L(n1), R(n2);
// 将左半部分复制到L,右半部分复制到R
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, j = 0, 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(std::vector<int>& arr, int l, int r) {
if (l < r) {
int m = l+(r-l)/2;
// 递归地对左右两侧进行排序
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
// 合并左右子序列
merge(arr, l, m, r);
}
}
int main() {
int A[] = {16, 25, 5, 8, 13, 1, 10, 3};
int n = sizeof(A) / sizeof(A[0]);
std::vector<int> vec(A, A+n); // 将数组转换为 vector,方便操作
mergeSort(vec, 0, n-1);
// 打印排序后的数组
for (int i : vec) {
std::cout << i << " ";
}
std::cout << "\n";
return 0;
}
```
请注意,这个代码片段需要在支持 C++ 的环境中运行,并且因为这是一个文本交互环境,我无法提供截图。你可以将这段代码复制到一个 .cpp 文件中,然后通过 C++ 编译器运行查看结果。
阅读全文