Java 按顺序插入数字到数组中

Question

我在完成作业时遇到问题。我对编码相当陌生，并且很难弄清楚如何做到这一点。我的教授提供了从数组中添加和删除项目的代码，但他希望我们添加一个方法，将项目添加到数组的正确位置。这是提供的代码：

import java.util.*;

public class MyArrayList {

private Object[]buffer;

private int currentSize;

public MyArrayList(){

   final int INITIAL_SIZE=10;

  buffer = new Object[INITIAL_SIZE];

  currentSize=0;

  }

public int size() {

  return currentSize;

  }

private void checkBounds(int n){

  if (n<0||n>= currentSize){

     throw new IndexOutOfBoundsException();

     }

  }

public Object get (int pos){

  checkBounds(pos);

  return buffer[pos];

  }

public Object remove(int pos){

  checkBounds(pos);

  Object removed = buffer[pos];

  for (int i = pos+1; i < currentSize; i++){

     buffer[i-1] = buffer[i];

  }

  currentSize--;

  return removed;

}

public boolean add(int pos, Object newElement){

  growBufferIfNecessary();

  currentSize++;

  checkBounds(pos);

  for(int i = currentSize - 1; i > pos; i--){

     buffer[i] = buffer [i-1];

  }

  buffer[pos] = newElement;

  return true;

}

public boolean addLast(Object newElement){

  growBufferIfNecessary();

  currentSize++;

  buffer[currentSize -1] = newElement;

  return true;

}

 private void growBufferIfNecessary(){

  if (currentSize==buffer.length){

     Object[] newBuffer = new Object[2*buffer.length];

     for(int i=0; i<buffer.length; i++){

     newBuffer[i] = buffer[i];

     }

  buffer = newBuffer;

   }

} 

}

这是我们的任务：

添加一个名为“public void insert(int n)”的方法，该方法会将 n 添加到 MyArrayList 对象中保持排序顺序的正确位置。使用现有的 MyArrayList 类并进行必要的修改。这是一个测试用例：

MyArrayList 列表 = new MyArrayLst();

列表.插入(5); 插入（10）；插入（8）；插入（20）；插入（6）；

如果您现在打印列表，它应该打印为：

5

6

8

10

20

这就是到目前为止我的主要方法中的内容：

 import java.util.*;

 public class ArrayListHomework {

 public static void main (String[]args){

 MyArrayList list = new MyArrayList();

 list.insert(5);

 list.insert(10);

 list.insert(8);

 list.insert(20);

 list.insert(6);

 for (int i=0; i<list.size(); i++){

     System.out.println(list.get(i));

   }

  }  

 }

我非常不知道如何启动这个插入方法。任何帮助，将不胜感激。谢谢。

Answer 1

可悲的是，不可原谅的是，你的“教授”提供的代码在add()方法中存在一个错误，如下：public boolean add(int pos, Object newElement){     growBufferIfNecessary();     currentSize++;     checkBounds(pos);         // rest of method因为checkBounds()不是首先调用，所以如果pos超出范围，currentSize将增加（并且缓冲区不必要地增长），使实例处于不一致/错误状态。编码101：首先检查参数。修理：public boolean add(int pos, Object newElement){     checkBounds(pos);     growBufferIfNecessary();     currentSize++;         // rest of method要回答您的问题，您必须实现所谓的插入排序。简而言之，这意味着使用循环迭代所有元素，并在遇到更大元素或到达元素末尾时插入新元素。请注意，如果您的数组元素尚未排序，则调用insert()毫无意义。要处理这种情况，您应该考虑抛出IllegalStateExceptionif 元素无序（您可以在迭代时检查前一个元素是否不大于当前元素）。

Answer 2

不完全像插入排序，因为有空值的空闲空间public void insert( int n ) {&nbsp; growBufferIfNecessary();&nbsp; for( int i = 0; i < buffer.length; i++ ) {&nbsp; &nbsp; if( buffer[i] == null ) {&nbsp; &nbsp; &nbsp; buffer[i] = n; currentSize++;&nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; }&nbsp; &nbsp; else if( buffer[i + 1] != null ) {&nbsp; &nbsp; &nbsp; int n1 = ((Number)buffer[i]).intValue();&nbsp; &nbsp; &nbsp; int n2 = ((Number)buffer[i + 1]).intValue();&nbsp; &nbsp; &nbsp; if( n1 < n && n2 > n ) {&nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy( buffer, i + 1, buffer, i + 2, currentSize - i - 1 );&nbsp; // line 1&nbsp; &nbsp; &nbsp; &nbsp; buffer[i + 1] = n; currentSize++;&nbsp; // line 2&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }}该add()函数可以替换第 1 行和第 2 行

Answer 3

感谢大家的帮助和建议。我通过使用 Marco13 建议的代码让它工作： https:&nbsp;//codereview.stackexchange.com/questions/36221/binary-search-for-inserting-in-array#answer-36239&nbsp;希望每个人都有美好的一天并快乐编程。-TJ