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）；如果您现在打印列表，它应该打印为：5681020这就是到目前为止我的主要方法中的内容： 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 ) {

  growBufferIfNecessary();

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

    if( buffer[i] == null ) {

      buffer[i] = n; currentSize++;

      break;

    }

    else if( buffer[i + 1] != null ) {

      int n1 = ((Number)buffer[i]).intValue();

      int n2 = ((Number)buffer[i + 1]).intValue();

      if( n1 < n && n2 > n ) {

        System.arraycopy( buffer, i + 1, buffer, i + 2, currentSize - i - 1 );  // line 1

        buffer[i + 1] = n; currentSize++;  // line 2

        break;

      }

    }

  }

}

该add()函数可以替换第 1 行和第 2 行

Answer 3

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