带有对象数组列表的Java插入排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23503921/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Insertion Sort with an Array List of objects?
提问by TechnoSam
I have a class Card which contains value (int), suit (String) and faceValue (String). It seems like a regular insertion sort on Card.value should work fine. I just use the whole object when moving things around. For some reason, this crashes and burns. It ends up duplicating the highest card into every element except for a random element that I can't understand.
我有一个类 Card，其中包含 value (int)、suit (String) 和 faceValue (String)。似乎 Card.value 上的常规插入排序应该可以正常工作。我只是在移动东西时使用整个对象。出于某种原因，这会崩溃并烧毁。它最终将最高的卡片复制到每个元素中，除了一个我无法理解的随机元素。
value, suit, and faceValue are pulic, also.
value、suit 和 faceValue 也是公开的。
This is my code:
这是我的代码：
public static void insertionSort(ArrayList<Card> Array) {
int i,j;
Card key = new Card(0, "","");
for (i = 1; i < Array.size(); i++) {
key.value = Array.get(i).value;
key.suit = Array.get(i).suit;
key.faceValue = Array.get(i).faceValue;
j = i;
while((j > 0) && (Array.get(j - 1).value > key.value)) {
Array.set(j,Array.get(j - 1));
j--;
}
Array.set(j,key);
}
}
I checked this against Wikipedia's pseudo code, and I can't find any fundamental difference. I've been through the debugger a dozen times, and I can't see any reason for the compiler to do what it's doing. Does anyone have an idea why it's not working?
我根据维基百科的伪代码检查了这个，我找不到任何根本区别。我已经通过调试器十几次了，我看不出编译器有什么理由去做它正在做的事情。有谁知道为什么它不起作用？
Thanks.
谢谢。
采纳答案by Kicsi
At every cycle, you insert the object "key" into the list (Array.set(j,key);). So, at the end your whole list will be made of references to the object "key". So when you set key.value, key.suit and key.faceValue at the end, you are setting the fields of every element of your list, because your list consists of references of the same object.
在每个循环中，您将对象“key”插入列表 (Array.set(j,key);)。因此，最后您的整个列表将包含对对象“key”的引用。因此，当您在最后设置 key.value、key.suit 和 key.faceValue 时，您正在设置列表中每个元素的字段，因为您的列表由同一对象的引用组成。
move Card key = new Card(0, "",""); inside the for cycle. Like this:
move Card key = new Card(0, "",""); 在 for 循环中。像这样：
public static void insertionSort(ArrayList<Card> Array) {
int i,
j;
for (i = 1; i < Array.size(); i++) {
Card key = new Card(0, "","");
key.value = Array.get(i).value;
key.suit = Array.get(i).suit;
key.faceValue = Array.get(i).faceValue;
j = i;
while((j > 0) && (Array.get(j - 1).value > key.value)) {
Array.set(j,Array.get(j - 1));
j--;
}
Array.set(j,key);
}
}
gl with your studies :)
gl与您的学习:)
回答by Dmitry Ginzburg
You're setting all the fields of Array(OMG, please rename it!) with the same element: key. So, all the elements would be the same.
您正在Array使用相同的元素设置（OMG，请重命名！）的所有字段：key. 所以，所有的元素都是一样的。
回答by DRAX
I would like to extend ginz's answer.
我想扩展ginz的答案。
Java objects are passed by reference. So you are changing one object and setting it to multiple indexes.
Java 对象是通过引用传递的。因此，您正在更改一个对象并将其设置为多个索引。
To visualize (beforeand after):
可视化（之前和之后）：
For after: Please note that not all indexes must reference to same object. Some of them could remain unchanged.
对于after：请注意，并非所有索引都必须引用同一个对象。其中一些可以保持不变。
Better approach would be to move objects, instead of trying to duplicate them.
更好的方法是移动对象，而不是尝试复制它们。
Also, by Java standard, name of properties (variables) should always start with small letter.
此外，根据 Java 标准，属性（变量）的名称应始终以小写字母开头。
Here is working code:
这是工作代码：
public static void insertionSort(ArrayList<Card> array) {
int i, j;
for (i = 1; i < array.size(); i++) {
Card tmp = array.get(i);
j = i;
while ((j > 0) && (array.get(j - 1).value > tmp.value)) {
array.set(j, array.get(j - 1));
j--;
}
array.set(j, tmp);
}
}
回答by njzk2
The basic algorithm is
基本算法是
- for each element
- search for the first smaller element going downward
- insert element right after that
- 对于每个元素
- 搜索向下的第一个较小的元素
- 在此之后插入元素
So, in your case:
所以，在你的情况下：
public static void insertionSort(ArrayList<Card> cards) {
for (int i = 1; i < cards.size(); i++) {
int value = cards.get(i).value;
j = i;
for (j = i-1; j >= 0; j--) {
if (cards.get(j).value <= key.value) {
break;
}
}
cards.add(j,cards.remove(i));
}
}
One important point here is that at no point does the array contains duplicated values (which happens when you use set)
这里重要的一点是，数组在任何时候都不会包含重复的值（当您使用时会发生这种情况set）
