動態數組未正確初始化

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〜中間成爲排序的數組而不是左右之間的範圍。

你試圖索引到合適的陣列參數右 ...這總是會比右邊的數組元素的數量大，因爲你分配它有權 - 中間元素。

您的MergeSort函數中也有錯誤。您從來沒有真正排序中間因素，因爲合併功能陣列[右]從未加入的RArray在，所以第一個遞歸調用不會對它進行排序，而你正在傳遞中間+ 1到第二次遞歸調用，所以它沒有對它進行排序。