java 将元素插入排序列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13776593/
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
Inserting an element into a sorted list
提问by Russell Cargill
Ok I'm using getSharedPreferences to store my high score but before I fill it up I wanted to sort the scores into ascending order via and array, but if it finds a Score less than it in the first pos then it wont check the rest for the smallest?
好的，我正在使用 getSharedPreferences 来存储我的高分，但在我填写它之前，我想通过和数组将分数按升序排序，但是如果它在第一个 pos 中找到比它小的分数，那么它不会检查其余的最小的？
//function to add score to array and sort it
public void addscoretoarray(int mScore){
for(int pos = 0; pos< score.length; pos++){
if(score[pos] > mScore){
//do nothing
}else {
//Add the score into that position
score[pos] = mScore;
break;
}
}
sortArray(score);
}
should I call sortArray() before and after the loop to fix this problem or is there a better method to achieve the same results?
我应该在循环之前和之后调用 sortArray() 来解决这个问题还是有更好的方法来实现相同的结果？
I should also mention that the sortArray(score) function is just calling Arrays.sort(score) where score is an array of mScore
我还应该提到 sortArray(score) 函数只是调用 Arrays.sort(score) ，其中 score 是 mScore 的数组
EDIT: based on what @Vincent Ramdhanie posted I have revised the post:
编辑：根据@Vincent Ramdhanie 发布的内容，我修改了帖子：
public void addscoretoarray(int mScore){
int pos = score.length;
//sort the array (in ascending order)
sortArray(score);
//go though the array( in descending order) and check for a place that suits the conditions
while(pos>=0 && score[pos] > mScore){
pos--; //do nothing as score[pos] is larger than mScore
}
//so once a pos is found (e.g. broke out of the while loop)
//check that it is still in the list
if(pos >= 0){
//if it is then move everything down 1 position
for(int i = 0; i < pos; i++){
score[i] = score[i+1];
}
//replace the initial pos with the new score
score[pos] = mScore;
}
}
I still believe that it will drop off the list when in the for(int i = 0; i < pos; i++){loop.
我仍然相信它会在for(int i = 0; i < pos; i++){循环中退出列表。
采纳答案by Vincent Ramdhanie
Why not keep the array of scores sorted. So your add score to array will assume that the array is sorted in descending order all the time. The new score to be inserted will simply push the lowest score off the array as it is inserted. You can then use an insert algorithm something like this:
为什么不保持排序的分数数组。因此，您向数组添加分数将假定数组始终按降序排序。要插入的新分数将在插入数组时简单地将最低分数从数组中删除。然后，您可以使用类似这样的插入算法：
insertScore(int[] scores, int mscore){
//find insert point
int i = 0;
while(i < scores.length && scores[i] > mscore){
i++;
}
if(i < scores.length){
//you found a place to insert the score
for(int j = scores.length-1; j > i; j--){
scores[j] = scores[j - 1];
}
scores[i] = mscore;
}
}
In this case there is no need to resort the array.
在这种情况下，不需要重新使用数组。
回答by Evgeniy Dorofeev
If I understood your correctly then I suggest this
如果我理解正确，那么我建议这样做
int[] a1 = { 1, 2, 3, 4, 6 };
int mScore = 5;
int[] a2 = new int[a1.length + 1];
Arrays.sort(a1);
int p = Arrays.binarySearch(a1, mScore);
if (p < 0) {
p = -p - 1;
System.arraycopy(a1, 0, a2, 0, p);
System.arraycopy(a1, p, a2, p + 1, a1.length - p);
a2[p] = mScore;
}
System.out.println(Arrays.toString(a2));
output
输出
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
Note that it inserts only unique values
请注意，它仅插入唯一值
回答by Grigory Kislin
See javadoc to @return of binarySearch:
请参阅javadoc 到 @return of binarySearch：
Returns the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
返回搜索键的索引，如果它包含在列表中；否则，(-(插入点) - 1)。插入点定义为将键插入列表的点：大于键的第一个元素的索引，如果列表中的所有元素都小于指定的键，则为 list.size()。请注意，这保证当且仅当找到键时返回值将 >= 0。
回答by Rahul
public void addscoretoarray(int mScore){
for(int pos = 0; pos< score.length; pos++){
if(score[pos] > mScore){
//do nothing
}else {
//Add the score into that position
score[pos] = mScore;
break;
}
}
sortArray(score);
}
there are some major bugs in the code.
代码中有一些主要错误。
score[pos] = mScore;in this statement, you are assigningmScoreat positionposwhich will result in the value stored atposbeing lost.If you are using an array, then to store any element in between, you need to move all the remaining elements 1 position to the right, which you are not doing here.
score[pos] = mScore; break;
score[pos] = mScore;在此语句中，您正在分配mScore位置pos，这将导致存储的值pos丢失。如果您使用的是数组，那么要存储其间的任何元素，您需要将所有剩余元素向右移动 1 个位置，您在这里没有这样做。
score[pos] = mScore; break;
the break will break the loop in the first iteration itself, after storing the element at pos.
在将元素存储在 pos 之后，break 将在第一次迭代中中断循环。
Suggestion :
建议 ：
Use arraylist instead of native array. Modified pseudo code:
使用 arraylist 而不是本机数组。修改后的伪代码：
public void addscoretoarray(int mScore){
int index = getFirstIndexOfScoreGreaterThanmScore(); // need to implement it
if(index == -1){ // no element greater than mscore
score.add(mScore);
}else{
score.add(index,mScore);
}
// sortArray(score); // no need to call this if the list is initially empty as the insertion will be in sorted order itself
if(score.length == maxSize){
//do whateverwhen the list is full as per your requirements
}
}
