合并两个有序数组cpp
时间: 2023-09-13 16:04:12 浏览: 71
可以使用双指针法,从两个数组的末尾开始比较,将较大的数放入合并后的数组的末尾,直到其中一个数组遍历完毕,再将另一个数组中剩余的元素依次放入合并后的数组中。
以下是基于双指针法的合并两个有序数组的C++代码实现:
```c++
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
```
其中,`i`和`j`分别指向两个数组末尾,`k`指向合并后的数组末尾。在循环中,如果`nums1[i]`大于`nums2[j]`,则将`nums1[i]`放入合并后的数组的末尾,否则将`nums2[j]`放入合并后的数组的末尾。最后,如果数组`nums2`还有剩余的元素,将其依次放入合并后的数组中。
相关问题
用C++写一段用于合并两个有序数组的代码
以下是使用C++编写的合并两个有序数组的代码例:
```cpp
#include <iostream>
<vector>
std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
std::vector<int> mergedArray;
int i = 0; // Pointer for the first array
int j = 0; // Pointer for the second array
// Compare elements of both arrays and insert them into the new array in sorted order
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] <= arr2[j]) {
mergedArray.push_back(arr1[i]);
i++;
} else {
mergedArray.push_back(arr2[j]);
j++;
}
}
// Insert the remaining elements from the first array
while (i < arr1.size()) {
mergedArray.push_back(arr1[i]);
i++;
}
// Insert the remaining elements from the second array
while (j < arr2.size()) {
mergedArray.push_back(arr2[j]);
j++;
}
return mergedArray;
}
int main() {
// Example usage
std::vector<int> arr1 {1, 3, 5, 7};
std::vector<int> arr2 {2, 4, 6, 8};
std::vector<int> mergedArr = mergeSortedArrays(arr1, arr2);
// Output the merged array
for (int i = 0; i < mergedArr.size(); i++) {
std::cout << mergedArr[i] << " ";
}
return 0;
}
```
在主函数中,我们创建了两个已排序的数组`arr1`和`arr2`,并调用`mergeSortedArrays`函数将它们合并到`mergedArr`中。最后,我们使用循环遍历`mergedArr`并输出合并后的数组元素。运行该程序将输出合并后的有序数组:1 2 3 4 5 6 7 8。
用C++实现一个无序数组的两路合并排序
好的,以下是一个使用C++实现的无序数组的两路合并排序的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < k; ++p) {
arr[left + p] = temp[p];
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
vector<int> arr = {3, 9, 2, 4, 8, 5, 1};
mergeSort(arr, 0, arr.size() - 1);
for (auto num : arr) {
cout << num << " ";
}
return 0;
}
```
在上述代码中,`merge`函数用于合并两个有序数组,`mergeSort`函数用于将无序数组不断划分为更小的子问题,直到只剩下一个元素为止,然后利用`merge`函数将子问题合并成更大的有序数组。最后在`main`函数中调用`mergeSort`函数对无序数组进行排序,输出有序数组。
运行结果:
```
1 2 3 4 5 8 9
```