c++ - 动态数组未正确初始化

Question

我正在编写一个程序，它使用两个动态数组对原始数组进行排序:一个用于左侧，一个用于右侧。

但是，动态数组在第 23 行和第 28 行不接收原始数组(如整个数组中的 cout 方法所示)。它们要么是空的，要么包含超出范围的元素。因此，该程序不能作为一个整体运行。那么我的问题是，是初始化本身的问题，还是第 18-19 行的声明的问题？我个人认为它与声明有关，但我不确定我应该用它做什么，就像动态数组一样，我不想把大小搞得太多。我包括了所有正确测试的方法，但如果认为它们是不必要的，我会编辑这个问题。预先感谢您的帮助。

#include "stdafx.h"
#include <iostream>
using namespace std;

void Merge(int *array, int left, int middle, int right)
{
int * LArray;
int * RArray;
int counter = left;//This counter is used as a marker for the main array.
int mid = middle;

cout<<"Left " << left << "middle: "<< middle << " right: " << right<<endl;

LArray = new int[middle-left + 1];
RArray = new int[right];

/*Initializes LArray*/
for (int i = left; i < middle - left + 1; i++)
{
    LArray[i] = array[i];
}

/*Initializes RArray*/
int temp = 0;
for (int i = middle; i < right; i++)
{
    RArray[temp] = array[i];
    temp++;
}

/*Prints out LArray*/
cout<<"LARRAY: ";
for (int i = left; i < middle- left + 1; i++)
{
    cout<<LArray[i]<< " ";
}

/*Prints out RArray*/
cout<<endl<<"RARRY: ";
temp = 0;
for (int i = middle; i < right; i++)
{
    temp = 0;
    cout<<RArray[temp]<< " ";
    temp++;
}
cout<<endl;

while (left <= middle && mid <= right)
{
    /*This if statement checks if the number in the left array is smaller than the number in the right array*/
    if (LArray[left] < RArray[right])
    {
        array[counter] = LArray[left];
        left++;
        counter++;
        cout<<"First if: array[counter]: "<< array[counter]<<" LArray[left]" << LArray[left]<<" left: "<< left<<" counter : "<< counter<<endl;
    }
    /*This else statement checks if the number in the right array is smaller than the number in the left array*/
    else
    {
        array[counter] = RArray[right];
        mid++;
        counter++;
        cout<<"    First else: array[counter]: "<< array[counter] <<  " RArray[right] "<< RArray[right]<<" mid: "<< mid<<" counter : "<< counter<<endl;
    }
}
/*If RArray is completed, check this one for any remaining elements.*/
while (left <= middle)
{
    array[counter] = LArray[left];
    left++;
    counter++;
    cout<<" First while: array[counter]: "<< array[counter]<<" LArray[left]" << LArray[left]<<" left: "<< left<<" counter : "<< counter<<endl;
}

/*If LArray is completed, check this one for any remaining elements.*/
while (mid <= right)
{
    array[counter] = RArray[right];
    mid++;
    counter++;
    cout<<"  Second while: array[counter]: "<< array[counter] <<  " RArray[right] "<< RArray[right]<<" mid: "<< mid<<" counter : "<< counter<<endl;
}

delete [] LArray;
delete [] RArray;

}


void MergeSort( int *array,int left, int right ) 
{ 
if ( left < right ) 
{ 
    int middle = ( left + right ) / 2;
    MergeSort( array, left, middle ); 
    MergeSort( array, middle + 1, right ); 
    Merge( array, left, middle, right ); 
} 
};

/*Checks if the array listed is sorted by looping through and checking if the current number is smaller than the previous.*/
bool IsSorted(int* array, unsigned long long size)
{

for (int i = 0; i < size; i++)
{
    cout<<array[i]<< " ";
}
cout<<endl;
for (int i = 1; i < size; i++)
{
    if (array[i] < array[i-1])
        return false;
}
return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
int array[8] = {5, 2, 4, 7, 1, 3, 2, 6};
MergeSort(array, 0, 8);

bool check = IsSorted(array, 8);

if (check)
    cout<<"It is sorted!";
else
    cout<<"It is not sorted!";
return 0;
}

Answer 1

合并排序的思想是递归地将一个数组分成两半，对这两半进行排序，然后将它们合并回一起。

以下是我在您的代码中发现的问题:

不是你的算法问题的代码怪异:

您的左侧数组总是比必要的大，因为您将它分配给具有中间 元素并按此初始化它。

你初始化右数组两次。

你算法的实际问题:

你没有正确初始化计数器，它总是被设置为 0 所以无论你在调用堆栈中有多深，你总是将元素 0 到 middle 设置为排序数组而不是左右之间的范围。

您正在尝试使用参数 right 索引到正确的数组中...它总是比 right 数组中的元素数量大，因为您将其分配为具有 right -中间元素。

您的 MergeSort 函数也有错误。您实际上从未对 middle 元素进行排序，因为在 Merge 函数中 array[right] 从未添加到 RArray，因此第一个递归调用获胜'sort it, and you're passing in middle + 1 to the second recursive call so it's not sorting it.