Visual C++合併排序

我想弄清楚爲什麼下面的代碼不會做合併排序。代碼編譯得很好，沒有運行時錯誤。 SortCollection方法只返回一個未排序的數組。沒有編譯錯誤和沒有運行時錯誤，只是返回一個未排序的數組。任何指針都會受到極大的關注。Visual C++合併排序

#include "stdafx.h" 
#include <deque> 
#include <climits> 
#include <stdio.h> 

using namespace System; 
using namespace System::Collections; 
using namespace System::Collections::Generic; 

generic <typename T> where T: IComparable<T> 
ref class MergeSort 
{ 
public: 
// constructor 
MergeSort(){} 

// SortCollection() method 
array<T>^ SortCollection(array<T>^ inputArray) 
{ 
    int n = inputArray->Length; 
    if (n <= 1) 
    { 
     return inputArray; 
    } 
    array<T>^ array1 = gcnew array<T>(inputArray->Length/2); 
    array<T>^ array2 = gcnew array<T>(inputArray->Length - array1->Length); 
    int array1Count = 0; 
    int array2Count = 0; 
    for (int i = 0; i < n; i++) 
    { 
     if (i < n/2) 
     { 
      array1[array1Count] = inputArray[i]; 
      array1Count++; 
     } 
     else 
     { 
      array2[array2Count] = inputArray[i]; 
      array2Count++; 
     } 
    } 
    SortCollection(array1); 
    SortCollection(array2); 
    array<T>^ newArray = gcnew array<T>(inputArray->Length); 
    delete inputArray; 
    return Merge(newArray, array1, array2); 
} 

array<T>^ Merge(array<T>^ targetArray, array<T>^ array1, array<T>^ array2) 
{ 
    int n1 = array1->Length; 
    int n2 = array2->Length; 
    int x1 = 0; 
    int x2 = 0; 
    int counter = 0; 
    while (x1 < n1 && x2 < n2) 
    { 
     if (array1[x1]->CompareTo(array2[x2]) < 0) 
     { 
      targetArray[counter] = array1[x1]; 
      x1 ++; 
      counter++; 
     } 
     else 
     { 
      targetArray[counter] = array2[x2]; 
      x2 ++; 
      counter++; 
     } 
    } 
    while (x1 < n1) 
    { 
     targetArray[counter] = array1[x1]; 
     counter ++; 
     x1 ++; 
    } 
    while (x2 < n2) 
    { 
     targetArray[counter] = array2[x2]; 
     counter ++; 
     x2 ++; 
    } 
    return targetArray; 
} 
};

來源

2013-02-16 deadEddie

嗯......但是你打印/測試什麼？原始數組還是什麼Sort返回？不管怎樣，試試這個：

SortCollection(array1);     
SortCollection(array2);   
// array<T>^ newArray = gcnew array<T>(inputArray->Length); 
// delete inputArray;     ---> "reuse" the input array   
return Merge(inputArray, array1, array2);

編輯：我敢肯定你知道這一點，但你只需要支付更多的關注。

「正常」功能拍攝參數和返回結果，而不改變參數：

Y=f(x);

你期望x是因爲以前的，結果在y。這些都是很好的功能。但是一些功能會改變論點。有時很明顯，就像在

Destroy(x);

但經常不是很明顯，就像在

y=sort(x);

傳遞x「按值」是保證不被改變，但是如果函數取類似的參考（如type^ x）它可以直接訪問原始變量並可以更改其內容。這種雙重性是你所擁有的（在SortCollection和Merge）。您需要決定，並且「文檔」您的函數返回什麼以及如何修改它所採用的參數。

在一個版本中（與delete），您修改參數刪除它 !!!這通常不是一個好主意，必須要有很好的記錄。並且排序的數組作爲「返回值」傳遞（這也是一種真正的參考）。這個版本修改了參數，但結果是返回的（這就是你需要使用/ test/print的東西）。

沒有刪除的版本通過將已排序的數組放入其中來修改參數。在這種情況下，它可能完全是你想要的。無論如何 - 記錄它！它也返回對排序數組的引用 - 對參數。這是爲了方便而完成的，但爲了更好的可讀性可以排除，而「返回」只是無效。

第三種變體可以是，不修改參數，並返回排序後的數組。

來源

2013-02-17 00:02:14 qPCR4vir

非常感謝，你的建議解決了我的問題。顯然更高效。我試圖弄清楚，爲什麼它在我重新使用原始數組時工作，但在傳遞相同大小的新數組時不起作用。如果你有一個想法，我會欣賞一點額外的理解！ – deadEddie 2013-02-17 02:06:08

@deadEddie你打印/測試什麼？ ..見編輯 – qPCR4vir 2013-02-18 09:50:49

這裏有一個問題：

SortCollection(array1);    // array1 is deleted?? 
SortCollection(array2);    // you dont use any result from here? 
array<T>^ newArray = gcnew array<T>(inputArray->Length); 
delete inputArray;     // sort, deleted input array ! 
return Merge(newArray, array1, array2);

這裏是正確的？

array1=SortCollection(array1);     
array2=SortCollection(array2);   
array<T>^ newArray = gcnew array<T>(inputArray->Length); 
delete inputArray;      
return Merge(newArray, array1, array2);

來源

2013-02-16 21:28:06 qPCR4vir

沒有骰子。仍然得到一個未排序的數組作爲retult – deadEddie 2013-02-16 22:28:09

Visual C++合併排序

回答

相關問題