#include <iostream>
void merge(int arr[], const int l, const int r, const int m);
void merge_sort(int arr[], const int l, const int r);
int main()
{
int arr[8] = {2, 4, 1, 0, 7, 9, 5, 3};
merge_sort(arr, 0, 7);
for (int i = 0; i < 8; i++)
{
std::cout << arr[i] << '\n';
}
return 0;
}
void merge(int arr[], const int l, const int r, const int m)
{
int *left = new int[m - l];
int *right = new int[r - m + 1];
int i, j, k;
for (i = l; i < m; i++)
{
left[i - l] = arr[i];
}
for (i = m; i <= r; i++)
{
right[i - m] = arr[i];
}
i = j = 0;
k = l;
while (i < (m - l) && j < (r - m + 1))
{
if (left[i] < right[j])
{
arr[k] = left[i];
i++;
k++;
}
else
{
arr[k] = right[j];
j++;
k++;
}
}
while (i < (m - l))
{
arr[k] = left[i];
i++;
k++;
}
while (j < (r - m + 1))
{
arr[k] = right[j];
j++;
k++;
}
}
void merge_sort(int arr[], int l, int r)
{
int m = (l + r) / 2;
if (l < r)
{
int m = (l + r) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
逻辑有问题,左序数组的大小应该是m-l+1,右序数组的大小是r-m,代码修改如下:
#include <iostream>
void merge(int arr[], const int l, const int r, const int m);
void merge_sort(int arr[], const int l, const int r);
int main()
{
int arr[8] = {2, 4, 1, 0, 7, 9, 5, 3};
merge_sort(arr, 0, 7);
for (int i = 0; i < 8; i++)
{
std::cout << arr[i] << '\n';
}
return 0;
}
void merge(int arr[], const int l, const int r, const int m)
{
int *left = new int[m - l+1];
int *right = new int[r - m ];
int i, j, k;
for (i = l; i <= m; i++)
{
left[i - l] = arr[i];
}
for (i = m+1; i <= r; i++)
{
right[i - m-1] = arr[i];
}
i = j = 0;
k = l;
while (i <= (m - l) && j < (r - m ))
{
if (left[i] < right[j])
{
arr[k] = left[i];
i++;
k++;
}
else
{
arr[k] = right[j];
j++;
k++;
}
}
while (i <= (m - l))
{
arr[k] = left[i];
i++;
k++;
}
while (j < (r - m ))
{
arr[k] = right[j];
j++;
k++;
}
delete[] left;
delete[] right;
}
void merge_sort(int arr[], int l, int r)
{
//int m = (l + r) / 2;
if (l < r)
{
int m = (l + r) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, r, m);//merge(arr, l, m, r);
}
}