我正在尝试对字符串的ArrayList进行mergesort。每个字符串都是一个x，y点，它们需要按x坐标进行排序。我正在尝试根据《算法》一书中的伪代码对其进行建模。但是，我很困惑如何为我的目的转换它（因为它处理数组，并且我需要它用于字符串的ArrayList）以及函数是否应该返回任何东西。
我的书提供的伪代码如下：
//"This algorithm sorts the array a[i],...,a[j] in nondecreasing order.
//It uses the merge algorithm."
//Input Parameters: a,i,j
//Output Parameter: a
mergesort(a,i,j) {
//if only one element, just return
if (i == j)
return
//divide a into two nearly equal parts
m = (i + j) / 2
//sort each half
mergesort(a, i, m)
mergesort(a, m + 1, j)
//merge the two sorted halves
merge(a, i, m, j)
}
//"This algorithm receives as input indexes i, m, and j, and an array a, where
//a[i],...,a[m] and a[m+1],...,a[j] are each sorted in nondecreasing order.
//These two nondecreasing subarrays are merged into a single nondecreasing
//array."
//Input Parameters: a,i,m,j
//Output Parameter: a
merge(a,i,m,j) {
p = i //index in a[i],...,a[m]
q = m+1 //index in a[m+1],...,a[j]
r = i //index in a local array c
while(p <= m && q <= j) {
//copy smaller value to c
if(a[p] <= a[q]) {
c[r] = a[p]
p = p + 1
}
else {
c[r] = a[q]
q = q + 1
}
r = r + 1
}
//copy remainder, if any, of first subarray to c
while(p <= m) {
c[r] = a[p]
p = p + 1
r = r + 1
}
//copy remainder, if any, of second subarray to c
while(q <= j) {
c[r] = a[q]
q = q + 1
r = r + 1
}
//copy c back to a
for r = i to j
a[r] = c[r]
}
我的尝试如下：
public static void mergesort(ArrayList<String> data, int i, int j)
{
//if only one element, just return
if(i == j)
{
return;
}
//divide data into two nearly equal parts
int m = (i + j) / 2;
//sort each half
mergesort(data, i, m);
mergesort(data, m + 1, j);
//merge the two sorted halves
merge(data, i, m, j);
}
public static void merge(ArrayList<String> data, int i, int m, int j) //1,3,5
{
int p = i; //index in data.get(i),...,data.get(m)
int q = m+1; //index in data.get(m + 1),...,data.get(j)
ArrayList<String> c = new ArrayList<String>(); //initialize local ArrayList<String> c
while(p <= m && q <= j)
{
String[] point = data.get(p-1).split(",");
String[] otherPoint = data.get(q-1).split(",");
if(Integer.parseInt(point[0]) <= Integer.parseInt(otherPoint[0]))
{
c.add(data.get(p-1));
p += 1;
}
else
{
c.add(data.get(q-1));
q += 1;
}
}
//copy remainder, if any, of first subarraylist to c
while(p <= m)
{
c.add(data.get(p-1));
p += 1;
}
//copy remainder, if any, of second subarrayList to c
while(q <= j)
{
c.add(data.get(q-1));
q += 1;
}
//copy c back to data
for(int x = 0; x < c.size(); x++)
{
data.set(x, c.get(x));
}
}
我尝试使用Strings
ArrayList作为它：数据= [“ 400,400”，“ 100,100”，“ 500,500”，“ 600,600”，“ 50,50”]
mergesort(data, 1, 5)应该将ArrayList排序如下：[“ 50,50”，“ 100,100”，“ 400,400”，“ 500,500”，“ 600,600”]
但这给了我：
[“ 50,50”，“ 600,600”，“ 500,500”，“ 600,600”，“ 50,50”]
我做错什么了吗？我只是无法将手指放在上面。
最佳答案
将data.set(x, c.get(x));更改为data.set(i+x-1, c.get(x));。
为了使代码更易于理解，因为对Java数组进行了0索引，为了简化起见，我当然会将所有索引都基于0，以避免包含所有这些(p-1)和(q-1)内容。
关于java - 带有坐标点的ArrayList <String>的Mergesort，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29765469/