用c++写一个二路归并、递归的归并排序、非递归的归并排序
时间: 2023-12-31 19:24:53 浏览: 27
以下是用C++实现的二路归并、递归的归并排序和非递归的归并排序的代码示例:
1. 二路归并排序:
```cpp
#include <iostream>
using namespace std;
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
void mergeSort(int arr[], int size) {
if (size <= 1) {
return;
}
int mid = size / 2;
int left[mid];
int right[size - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, size - mid);
merge(arr, left, mid, right, size - mid);
}
int main() {
int arr[] = {5, 2, 8, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, size);
cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
2. 递归的归并排序:
```cpp
#include <iostream>
using namespace std;
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
void mergeSort(int arr[], int size) {
if (size <= 1) {
return;
}
int mid = size / 2;
int left[mid];
int right[size - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, size - mid);
merge(arr, left, mid, right, size - mid);
}
int main() {
int arr[] = {5, 2, 8, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, size);
cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
3. 非递归的归并排序:
```cpp
#include <iostream>
using namespace std;
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
void mergeSort(int arr[], int size) {
for (int currSize = 1; currSize <= size - 1; currSize = 2 * currSize) {
for (int leftStart = 0; leftStart < size - 1; leftStart += 2 * currSize) {
int mid = min(leftStart + currSize - 1, size - 1);
int rightEnd = min(leftStart + 2 * currSize - 1, size - 1);
int left[currSize];
int right[rightEnd - mid];
for (int i = 0; i < currSize; i++) {
left[i] = arr[leftStart + i];
}
for (int i = 0; i < rightEnd - mid; i++) {
right[i] = arr[mid + 1 + i];
}
merge(arr, left, currSize, right, rightEnd - mid);
}
}
}
int main() {
int arr[] = {5, 2, 8, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, size);
cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```