时间戳

首页 > 解决方案 > 将对象添加到已排序的数组到正确的位置

java - 将对象添加到已排序的数组到正确的位置

问题描述

所以我有这个项目，我为我的目录类编写 add 方法，这个 add 方法需要使用插入排序将一个项目添加到排序数组到正确的位置，除非数组中没有任何内容，在这种情况下我只想正常添加。这整个项目必须使用一个数组，我不能使用数组列表或其他任何东西。

我在这里遇到的问题是我的程序目前的方式是，它只向我的数组添加一个对象，并且每次我在运行期间尝试添加一个新对象时，它都会替换已经存在的项目。我知道我的问题出在我的 while 循环体和我初始化位置变量的方式上。

这是我遇到问题的方法。

public void addItem(Item theItem)
    {
        int position = size;

        if(size != 0){
            while (position > 0 && theItem.compareTo(items[position - 1]) < 0){
                items[position] = items[position - 1];
                position--;
            }
            items[position] = theItem;
        }
        else{
        items[size] = theItem;
        size++;
    }

这是我的 compareTo 方法

public int compareTo(Item other){
        if(this.getItemType().equals(other.getItemType())){
           return this.itemnum - other.itemnum;
        }
        //item types are not equal
        else
        return this.getItemType().compareTo(other.getItemType());
        //try writing code to compare by price as well
    }

标签： java

解决方案

您的代码中最可能的问题是这一行：

items[position-1] = items[position];

这会将数组中的项目从当前位置复制到其左侧的位置。

当您插入新项目时，您希望将项目从左侧复制到当前位置，以便为左侧的新项目腾出空间。

将其更改为

items[position] = items[position-1];

A在块之后，在第一个块内size++也丢失了。whileif

addItem在下面的测试代码中添加第二个调用时，我意识到了这一点。

size++您还可以在语句之外放置一个if语句。

我用来修复它的完整、最小、可重现的示例。我使用Integer而不是Item避免添加更多类。

public class Main {
  private int size = 0;
  private Integer[] items = new Integer[20];

  public static void main(String... args) {
    new Main().execute();  // Moving us into a non-static context
  }

  public void execute() {
    System.arraycopy(new Integer[] {1,2,3,4,6,7,8,9}, 0, items, 0, 8);
    size = 8;
    // items = [1,2,3,4,6,7,8,9,null,null,...]

    addItem(5);
    addItem(5); // test adding a second item

    // items = [1,2,3,4,5,6,7,8,9,null,null,...]
    for (Integer i : items) {
      System.out.println(i);
    }
  }

  public void addItem(Integer item) {
    int position = size;
    if (size != 0) {
      while (position > 0 && item.compareTo(items[position - 1]) < 0) {
        // items[position-1] = items[position]; // Result [1,2,3,4,5,null,null,...]
        items[position] = items[position-1]; // Result [1,2,3,4,5,6,7,8,9,null,null,...]
        position--;
      }
      items[position] = item;
      size++; // this line was missing as well
    } else {
      items[size] = item;
      size++;
    }
    // or a single size++; here, removing the other two
  }
}

推荐阅读