所以我有这个项目，我正在为我的目录类编写add方法，这个add方法需要使用插入排序将一个项目添加到一个排序数组中的正确位置，除非数组中没有任何内容，否则我只想正常添加它。整个项目必须使用数组，我不能使用arraylist或其他任何东西。
我在这里遇到的问题是，按照我的程序目前的方式，它只向我的数组中添加一个对象，每次我在运行期间尝试添加一个新对象时，它都会替换已经存在的项。我知道我的问题在于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++;
}
这是我对方法的比较
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
}
代码中最可能出现的问题是这一行：
items[position-1] = items[position];
这将把数组中的一个项目从当前位置复制到它左边的位置
插入新项目时，您希望将项目从左侧复制到当前位置，以便为左侧的新项目腾出空间。
将其更改为
items[position] = items[position-1];
在第一个if块内的while块之后也缺少size++。
当我在下面的测试代码中添加对addItem的第二个调用时，我意识到了这一点。
您也可以在if语句之外放置一个size++语句。
一个完整的、最小的、可复制的例子，我试图修复它。我使用了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
}
}
制作新阵列的丑陋解决方案
public int[] addItem(int item, int[] items){
int[] tempArr = new int[items.length + 1];
boolean hasAlready = false;
for(int i = 0 ; i < items.length; i++){
if(hasAlready)tempArr[i + 1] = items[i];
else if(item < items[i]){
tempArr[i] = item;
tempArr[i + 1] = items[i];
hasAlready = true;
}else {
tempArr[i] = items[i];
}
}
//items = tempArr; if items is global variable
return tempArr;
}
可以使用现有的实用程序函数Arrays.binarySearch和System.arraycopy。你的循环是1关闭。
public void addItem(Item theItem) {
Comparator<Item> comparator = Comparator.comparing(Item::getItemType)
.thenComparingInt(it -> it.itemnum);
int position = Arrays.binarySearch(items, 0, size, theItem, comparator);
// If position >= 0 the item was found (maybe no need to insert?)
if (position < 0) {
position = ~position; // Insert position of not found item
}
System.arraycopy(items, position, items, position + 1, size - position);
items[position] = theItem;
size++;
}
二进制搜索结果为找到非负索引，或未找到负~索引。在这里，二进制搜索是在从0到大小(排除(的子数组上进行的。
与Roger Gustavsson 相同
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);
// 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) {
if (size == 0) {
items[size] = item;
size++;
return;
}
int position = size;
while (position > 0 && item.compareTo(items[position - 1]) < 0) {
items[position] = items[position - 1];
position--;
}
items[position] = item;
size++;
}
}
关于您正在努力实现的目标，我认为下一个解决方案将是您可以根据特定需求构建自己的解决方案的起点。我已经稍微改变了你的主方法，我不知道你的类是否实现了comparative/Comparator。
public void addItem(Item theItem) {
int position = position(items, theItem); // position is a method that finds best position for inseriton
if (items[position] == null){ // if items at best position is null then add new element there
items[position] = theItem;
} else{
items[size] = theItem; // if not add element at last position
swapUp(size); // and swap them up to perfect position.
}
size++;
}
找到最佳位置的方法如下所示。
private static int position(Item[] items, Item newItem) {
if (isEmpty(items))
return 0;
int pos=0;
int target=items.length-1;
while(pos < target){
int m = pos+(target-pos)/2;
if (items[m] !=null){
if(newItem.getNumber()>items[m].getNumber()){ // comparing depending on item number
pos=m+1;
}else{
target=m;
}
}else{
target = m;
}
}
return pos;
}
正如您所看到的，方法是根据项目编号来寻找位置，您可以根据您的类型进行更改，或者同时进行类型和编号比较。Swaping up是通过2方法处理的。
private void swapUp(int lastPosition){
if (lastPosition == -1){
return;
}
Item lastItem = items[lastPosition];
Item p = items[lastPosition-1];
if (lastItem.getNumber() < p.getNumber())
replace(lastPosition, lastPosition-1);
else
lastPosition = 0;
swapUp(lastPosition-1);
}
private void replace(int from, int to){
Item temporary = items[from];
items[from] = items[to];
items[to] = temporary;
}
我再次对数字进行比较，你可以实现任何你想要的比较。我看到了你之前的问题，并为你的课程建模
Music{number=1111, name='White and Nerdy', price=2.5, pro='"Weird Al" Yankovic'}
Music{number=2222, name='Amish Paradise', price=2.22, pro='"Weird Al" Yankovic'}
Music{number=3333, name='The Saga Begins', price=2.0, pro='"Weird Al" Yankovic'}
Movie{number=4444, name='UHF', price=9.99, pro='"Weird Al" Yankovic'}
Movie{number=5555, name='The Dark Crystal', price=8.99, pro='"Jim Henson'}
Movie{number=6666, name='Die Hard', price=13.99, pro='Bruce Willis'}
Movie{number=6969, name='The Adventures of Mr. Winky', price=9.99, pro='Richard Dickinson'}
Book{number=7777, name='When I Grow Up', price=7.98, pro='"Weird Al" Yankovic'}
Book{number=8888, name='The Chronicles of Pern: First Fall', price=5.99, pro='"Anne McCaffrey'}
Book{number=9999, name='Get gud you scrub', price=2.5, pro='Steve "Troll" Rathier'}
正如你所看到的，它们是按顺序排列的。