我的老师这周出去了,她给了我们这个合并排序代码。它是为int[]数组写的,我们应该为String[]数组写一个。
下面是她的代码:
public static void mergeSort(int[ ] a, int from, int to)
{ if (from == to) return;
int mid = (from + to) / 2;
// sort the first and the second half
mergeSort(a, from, mid);
mergeSort(a, mid + 1, to);
merge(a, from, mid, to); }// end mergeSort
public static void merge(int[ ] a, int from, int mid, int to)
{ int n = to - from + 1; // size of the range to be merged
int[ ] b = new int[n]; // merge both halves into a temporary array b
int i1 = from; // next element to consider in the first range
int i2 = mid + 1; // next element to consider in the second range
int j = 0; // next open position in b
// as long as neither i1 nor i2 past the end, move the smaller into b
while (i1 <= mid && i2 <= to)
{ if (a[i1] < a[i2])
{ b[j] = a[i1];
i1++; }
else
{ b[j] = a[i2];
i2++; }
j++;
}
// note that only one of the two while loops below is executed
// copy any remaining entries of the first half
while (i1 <= mid)
{ b[j] = a[i1];
i1++;
j++; }
// copy any remaining entries of the second half
while (i2 <= to)
{ b[j] = a[i2];
i2++;
j++; }
// copy back from the temporary array
for (j = 0; j < n; j++)
a[from + j] = b[j];
}// end merge
下面是我的尝试:
//merge sort
public static void mergeSort(String[] a, int from, int to)
{
if (from == to)
return;
int mid = (from + to) / 2;
// sort the first and the second half
mergeSort(a, from, mid);
mergeSort(a, mid + 1, to);
merge(a, from, mid, to);
}// end mergeSort
//work
public static void merge(String[] a, int from, int mid, int to)
{
int n = to - from + 1; // size of the range to be merged
String[]b = new String[n]; // merge both halves into a temporary array b
int i1 = from; // next element to consider in the first range
int i2 = mid + 1; // next element to consider in the second range
int j = 0; // next open position in b
// as long as neither i1 nor i2 past the end, move the smaller into b
while (i1 <= mid && i2 <= to)
{
if (a[i1].compareTo(a[i2]) > 0)
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++;
}
// note that only one of the two while loops below is executed
// copy any remaining entries of the first half
while (i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
// copy any remaining entries of the second half
while (i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}
// copy back from the temporary array
for (j = 0; j < n; j++)
a[from + j] = b[j];
}//end merge
我觉得她给我们的代码缺少了一些东西,她通常会在课堂上向我们解释,但由于她不在,我不知道该怎么做。任何帮助都是感激之情。谢谢!
1条答案
按热度按时间yjghlzjz1#
一切正常-只有
merge
中的compareTo
方向错误。