在我的代码中,lb
指的是下界,ub
指的是上限。我使用mergeSort function
将数组递归拆分为更小的部分,并按merge function
排序顺序合并。
#include <iostream>
using namespace std;
void merge(int input[], int lb, int ub, int size)
{
int i = lb;
int k = 0;
int mid = (lb + ub) / 2;
int j = mid + 1;
int *arr = new int[size];
while (i <= mid && j <= ub)
{
if (input[i] <= input[j])
arr[k++] = input[i++];
else
arr[k++] = input[i++];
}
while (i <= mid)
arr[k++] = input[i++];
while (j <= ub)
arr[k++] = input[j++];
for (k = 0; k < size; k++)
input[k] = arr[k];
}
void mergeSort(int input[], int size)
{
int lb = 0;
int ub = size - 1;
int mid;
if (size == 0)
{
return;
}
else if (lb < ub)
{
mid = (lb + ub) / 2;
mergeSort(input, mid - lb + 1);
mergeSort(input + mid + 1, ub - mid);
merge(input, lb, ub, size);
}
else
{
return;
}
}
int main()
{
int input[1000], length;
cin >> length;
for (int i = 0; i < length; i++)
cin >> input[i];
mergeSort(input, length);
for (int i = 0; i < length; i++)
{
cout << input[i] << " ";
}
}
您在合并函数的第一个 while 循环中使用了 i 而不是 j 。正确的代码如下
while (i <= mid && j <= ub) {
if (input[i] <= input[j])
arr[k++] = input[i++];
else
arr[k++] = input[j++];
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句