我正在嘗試使用 C# 中的哨兵來實作合并排序演算法。
我要排序的陣列：
int[] arr = { 9, 8, 7, 6, 5, 4 };
這是我的合并排序功能：
void MergeSort(int[] arr, int lowerIndex, int upperIndex)
{
if (upperIndex > lowerIndex)
{
int midIndex = (lowerIndex upperIndex) / 2;
MergeSort(arr, lowerIndex, midIndex);
MergeSort(arr, midIndex 1, upperIndex);
Merge(arr, midIndex, lowerIndex, upperIndex);
}
}
這是我的合并功能：
void Merge(int[] arr, int midIndex, int lowerIndex, int upperIndex)
{
int leftArrayLength = midIndex - lowerIndex 1;
int rightArrayLength = upperIndex - midIndex;
int[] left = new int[leftArrayLength 1];
int[] right = new int[rightArrayLength 1];
for (int i = 0; i < leftArrayLength; i )
{
left[i] = arr[i];
}
for (int j = 0; j < rightArrayLength; j )
{
left[j] = arr[midIndex j];
}
//Sentinels
left[leftArrayLength] = int.MaxValue;
right[rightArrayLength] = int.MaxValue;
int m = 0;
int n = 0;
for (int k = lowerIndex; k <= upperIndex; k )
{
if (left[m] <= right[n])
{
arr[k] = left[m];
m = 1;
}
else
{
arr[k] = right[n];
n = 1;
}
}
}
它給出了一個奇怪的輸出：
0 0 0 7 0 4
到目前為止，我已經按照 CLRS 中給出的偽代碼反復檢查了我的實作，但我沒有發現我的實作有什么問題。
請告訴我我做錯了什么。
uj5u.com熱心網友回復：
您在left/right陣列初始化中至少有以下幾個錯誤：
- 因為
left你應該從lowerIndex：
for (int i = 0; i < leftArrayLength; i )
{
left[i] = arr[lowerIndex i];
}
- 因為
right有兩個錯誤 - 1）陣列名稱的拼寫錯誤并使用left2）索引的“off-by-one error”
for (int j = 0; j < rightArrayLength; j )
{
right[j] = arr[midIndex 1 j];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/408341.html
標籤：
上一篇：按最后3位數字排序