ArrayList<String> 与坐标点的合并排序

Question

我正在尝试对字符串的 ArrayList 进行合并排序。每个字符串都是一个 x,y 点，需要按 x 坐标对它们进行排序。我正在尝试根据我的算法书中的伪代码对其进行建模。但是，我很困惑如何为我的目的转换它（因为它处理数组，我需要它用于字符串的 ArrayList）以及函数是否应该 return 任何东西。

我的书提供的伪代码如下：

//"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) 东西。

Answer 2

除了下面提到的部分合并方法 merge(ArrayList data, int i, int m, int j) 之外，您所做的一切都正确。 //将c复制回数据 for(int x = 0; x < c.size(); x++) { data.set(x, c.get(x)); }

您在这里将数据从 c 复制到错误位置的数据。由于您已将列表从 i 合并到 j，因此您也应该将数据从 c 复制到这个地方。

所以使用

   //copy c back to data
    for (int x = 0; x < c.size(); x++) {
        data.set(x+i-1, c.get(x));
    }

ArrayList<String> 与坐标点的合并排序

Mergesort For ArrayList<String> With Coordinate Points

java

sorting

merge

mergesort

arraylist