java - 合并排序值输出错误

Question

我正在尝试在 100 大小的 LinkedList 上实现合并排序，经过大量阅读和比较，似乎我的算法是正确的，但它只是输出错误的内容。代码如下

public class MergeSort 
{
static LinkedList<Integer> list = new LinkedList<>();
public static void main(String[] args)
{        
    //add ints to list
    for(int i = 0;i < 100; i++)
    {
        list.add(roll());
    }
    //print list as a table
    for(int i = 0; i < 100; i++)
    {
        if((i + 1) % 10 == 0)
        {
            System.out.println(list.get(i) + "\t");
        }
        else
        {
            System.out.print(list.get(i) + "\t");
        }
    }
    mergeSort(list);

    //put some space between printed tables
    System.out.println("");
    System.out.println("");

    //print list after sort
    for(int i = 0; i < 100; i++)
    {
        if((i + 1) % 10 == 0)
        {
            System.out.println(list.get(i) + "\t");
        }
        else
        {
            System.out.print(list.get(i) + "\t");
        }
    }
}
/*
Performs the mergesort
*/
static void mergeSort(LinkedList<Integer> ll)
{
    if(ll.size() > 1)
    {
        int tmp = ll.size() / 2;

        //this whole bit is to change the sublist of List type to a LinkedList
        List leftTmp = ll.subList(0, tmp);
        List rightTmp = ll.subList(tmp, ll.size());

        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();

        left.addAll(leftTmp);
        right.addAll(rightTmp);

        mergeSort(left);
        mergeSort(right);

        merge(ll, left, right);
    }
}
//performs the merge on the sublists from mergeSort
static void merge(LinkedList<Integer> o, LinkedList<Integer> l, LinkedList<Integer> r)
{
    int combo = l.size() + r.size();

    int t = 0;
    int tL = 0;
    int tR = 0;

    while(t < combo)
    {
        if((tL < l.size() && tR < r.size()))
        {
            if(l.get(tL) < r.get(tR))
            {
                o.set(t, tL);
                t++;
                tL++;
            }
            else
            {
                o.set(t, tR);
                t++;
                tR++;
            }
        }
        else
        {
            if(tL >= l.size())
            {
                while(tR < r.size())
                {
                    o.set(t, tR);
                    t++;
                    tR++;
                }
            }
            if(tR >= r.size())
            {
                while(tL < l.size())
                {
                    o.set(t, tL);
                    t++;
                    tL++;
                }
            }
        }
    }
}
/*
Performs a random roll for use in the list
Returns a random integer
*/
public static int roll()
{
    double d = Math.random() * 1000.0;
    int i = (int)d;
    return i;
}
}

它输出这个噪音

642 495 716 307 716 893 681 617 150 761 
350 87  564 566 301 40  951 350 804 961 
406 864 161 408 600 434 218 142 808 426 
623 77  935 370 924 881 615 193 518 798 
955 479 810 778 901 375 656 103 526 583 
352 459 768 839 925 885 267 443 497 65  
982 688 812 227 242 479 819 271 681 48  
364 844 315 438 623 781 649 332 918 690 
275 891 927 516 897 504 127 581 111 704 
492 942 525 110 102 915 33  881 331 256 


0   0   1   2   3   1   2   3   4   5   
4   5   6   7   6   7   8   8   9   9   
10  10  11  12  13  14  15  11  12  13  
14  15  16  17  16  17  18  18  19  19  
20  21  22  23  20  21  22  23  24  25  
24  25  26  26  27  28  29  27  28  29  
30  30  31  32  33  31  32  33  34  35  
34  35  36  37  36  37  38  38  39  39  
40  40  41  41  42  43  44  45  46  47  
42  43  44  45  46  47  48  49  48  49  

谁能告诉我为什么？我看了好几遍还是没搞明白。它甚至没有相同的值，它会更改它们，然后 KINDOF 将它们按正确的顺序排列。我哪里出错了？

Answer 1

当您编写o.set(t, tL)时，您将左侧列表的索引分配为合并列表的值。您要做的是将左侧列表的值分配给合并列表 - o.set(t, l.get(tL))。

这就是为什么你在“排序”列表中得到不同数字的原因。您得到了索引而不是原始值。