java - ArrayList 与坐标点的合并排序

Question

我正在尝试对字符串的 ArrayList 进行合并排序。每个字符串都是一个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));
    }
}

我尝试使用字符串的ArrayList:

data = ["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"]

我是不是做错了什么？我只是无法确定它。

Answer 1

将data.set(x, c.get(x));更改为data.set(i+x-1, c.get(x));.

为了让代码更容易理解，由于 java 数组是 0 索引的，为了简单起见，我肯定会将所有索引都基于 0 ，以避免所有这些 (p-1) 和 (q-1) 的东西。