归并排序问题
本文关键字:问题 归并排序 | 更新日期: 2023-09-27 18:06:58
我正在制作各种排序算法的菜单,现在我被困在归并排序。我在点击执行按钮后遇到了一个错误。我在TextBox1中输入了5个数字,在TextBox2中输入了另外一组5个数字。它说索引超出了数组的边界。我在代码上标出了它出现的地方。知道是什么问题吗?
private void ExeButton_Click(object sender, EventArgs e)
{
string[] numsInString = EntNum.Text.Split(' '); //split values in textbox
string[] numsInString1 = EntNum1.Text.Split(' ');
for (int j = 0; j < numsInString.Length; j++)
{
a[j] = int.Parse(numsInString[j]);
}
for (int j = 0; j < numsInString1.Length; j++)
{
b[j] = int.Parse(numsInString1[j]);
}
{
sortArray();
Display();
}
}
public void sortArray()
{
m_sort(0, 10 - 1);
}
public void m_sort(int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(left, mid);
m_sort(mid + 1, right);
merge(left, mid + 1, right);
}
}
public void merge(int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (a[left] <= a[mid]) //index was outside the bounds of the the array
{
b[tmp_pos] = a[left];
tmp_pos = tmp_pos + 1;
left = left + 1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
b[tmp_pos] = a[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i < num_elements; i++)
{
a[right] = b[right];
right = right - 1;
}
}
private void ClearButton_Click(object sender, EventArgs e)
{
richTextBox1.Clear();
}
public void Display()
{
int i;
String numbers = "";
for (i = 0; i < 10; i++)
numbers += a[i].ToString() + " ";
numbers += b[i].ToString() + " ";
richTextBox1.AppendText(numbers + "'n");
}
关于您的具体问题:a
是一个包含5个元素的数组,索引为0, 1, 2, 3, 4
,因此a[4]
是最后一个元素。从m_sort(0, 10 - 1) = m_sort(0, 9);
开始。在m_sort()
中,计算
mid = (right + left) / 2 = (9 + 0) / 2 = 4
和call
merge(left, mid + 1, right) = merge(0, 4 + 1, 9) = merge(0, 5, 9).
在merge(int left, int mid, int right)
你评估:
if (a[left] <= a[mid]) i.e. if (a[0] <= a[5])
所以你访问了a[5]
,这是越界的
我认为你的归并排序可以大大简化。你可以在网上或教科书上查阅许多关于算法的资源。
下面是一个简化合并的示例,假设每个列表都按照元素0的最大值排序:
int c[] = new int[a.Length + b.Length];
int aPos = 0;
int bPos = 0;
for(int i = 0; i < c.Length; i++)
{
if(a[APos] > b[bPos])
{
c[i] = a[Apos];
if(aPos < aPos.Length - 1)
aPos++;
}
else
{
c[i] = b[bPos];
if(bPos < bPos.Length - 1)
bPos++;
}
}
// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];
// number of elements in array
private int x;
// Merge Sort Algorithm
public void sortArray()
{
m_sort( 0, x-1 );
}
public void m_sort( int left, int right )
{
int mid;
if( right > left )
{
mid = ( right + left ) / 2;
m_sort( left, mid );
m_sort( mid+1, right );
merge( left, mid+1, right );
}
}
public void merge( int left, int mid, int right )
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while( (left <= left_end) && (mid <= right) )
{
if( a[left] <= a[mid] )
{
b[tmp_pos] = a[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while( left <= left_end )
{
b[tmp_pos] = a[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while( mid <= right )
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for( i = 0; i < num_elements; i++ )
{
a[right] = b[right];
right = right - 1;
}
}