Java实现Sorted List by Array的问题

Question

我编写的类的 add 方法似乎有问题。我想使用数组创建一个 SortedList，但我不知道问题出在哪里。这是我的代码：

public class SortedList {

    private Integer[] elements;
    private int size;
    private int capacity;

    public SortedList(int cap) {

        elements = new Integer[cap];

        if (cap > 0)
        {
            cap = capacity;
        }
        else
            capacity = 10;

    }

    public boolean isEmpty()
    {
        return size == 0;
    }

    public boolean isFull()
    {
        return size == capacity;
    }

    public int size()
    {
        return size;
    }

    public void doubleCapacity()
    {
        capacity = capacity * 2;
    }

    public void add(Integer el)
    {
        if(this.isEmpty())
        {
            elements[0] = el;
            size++;
        }

        else if(this.isFull())
        {
            this.doubleCapacity();
            for(int i = 0; i<this.size(); i++)
            {
                if(el >= elements[i])
                {
                    elements[i+2] = elements[i+1];
                    elements[i+1] = el;
                }

                else
                {
                    elements[i+1] = elements[i];
                    elements[i] = el;
                }
            }
            size++;
        }
        else
        {
            for(int i = 0; i<this.size(); i++)
            {
                if(el >= elements[i])
                {
                    elements[i+2] = elements[i+1];
                    elements[i+1] = el;
                }
                else
                {
                    elements[i+1] = elements[i];
                    elements[i] = el;
                }
            }
            size++;
        }

    }

    public String toString()
    {
        String s = "";
        s = s + "<SortedList[";
        for(int i = 0; i < this.size(); i++)
        {
            s = s + elements[i];
            if(i < this.size()-1)
                s = s + ",";
        }
        s = s + "]>";
        return s;
    }


    public static void main(String[] args)
    {
        SortedList sl = new SortedList(5);
        sl.add(3);
        //sl.add(2);
        sl.add(4);
        sl.add(5);
//      sl.add(6);
        System.out.println(sl.toString());
    }



}

如果我只将 2 个整数添加到列表中，我的代码就可以工作，但是当我尝试添加数字 3,4,5 时，我会得到 3,5,5...

可能是什么问题？谢谢..

Answer 1

公共类 SortedList {

private Integer[] elements;
private int size=0;
private int capacity;

public SortedList(int cap) {

    elements = new Integer[cap];

    if (cap > 0)
    {
        capacity = cap;
    }
    else
        capacity = 10;

}

public boolean isEmpty()
{
    return size == 0;
}

public boolean isFull()
{
    return size == capacity;
}

public int size()
{
    return size;
}

public void doubleCapacity()
{
    capacity = capacity * 2;
}

public void add(Integer el) throws Exception{
    elements[size] = el;
    size++;
    if(size>capacity){
        throw new Exception("Size Exceeded");
    }
}

public String toString()
{
    sort();
    String s = "";
    s = s + "<SortedList[";
    for(int i = 0; i < this.size(); i++)
    {
        s = s + elements[i];
        if(i < this.size()-1)
            s = s + ",";
    }
    s = s + "]>";
    return s;
}

public void sort(){
    for (int i=0; i <size()-1; i++) {
        if (elements[i] > elements[i+1]) {
            // exchange elements
            int temp = elements[i];
            elements[i] = elements[i+1];
            elements[i+1] = temp;
        }
    }
}

public static void main(String[] args)
{
    try {
        SortedList sl = new SortedList(5);
        sl.add(3);
        //sl.add(2);
        sl.add(6);
        sl.add(5);

// sl.add(6);
System.out.println(sl.toString());
} catch (异常前) {
Logger.getLogger(SortedList.class.getName()).log(Level.SEVERE, null, ex);
}
}

}

Answer 2

您的插入代码不起作用。

elements[i+1] = elements[i];
elements[i] = el;

elements[i+1] 的旧值会发生什么情况？

Answer 3

我建议对之前的解决方案进行以下更改。如果您只在 toString() 中调用 sort，那么当您在一行中有多个未排序的元素时，您的列表将很快变得混乱（现在您可以从 toString() 中删除 sort()）。它本质上是一种快速插入排序，一旦无法在列表中进行更多交换，就会终止。同样，正如 dty 所建议的，更快的选择是使用二分搜索来查找插入点。

<代码>
public void doubleCapacity(){

capacity = capacity * 2;
Integer temp[] = new Integer[capacity];
for (int i = 0; i < size; i++){
    temp[i] = elements[i];
}
elements = temp;

}

public void add(Integer el){

if(size+1>capacity){
    doubleCapacity();
}
elements[size] = el;
size++;
sort();
}

public void sort(){

//Iterates down the list until it's sorted.
for (int i=size()-2; i >= 0 && (elements[i] < elements[i+1]); i--) {
        // exchange elements
        int temp = elements[i];
        elements[i] = elements[i+1];
        elements[i+1] = temp;
}

}