由Java中的数组实现排序列表中的问题

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

公共类排序列表{

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（））; （Log.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（）方法，那么在一行中有多个未排序元素的情况下，您的列表将快速失序（现在您可以从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; 
} 

}