Java里有10个数,已经按从大到小的顺序排序,输人一个数,将它插人到原有 数列中并保持从大到小的顺序不变,输出该数插人的位置。
时间: 2024-10-10 21:08:49 浏览: 32
Java Sorting:一个基准测试5种不同排序算法的程序。-开源
在Java中,如果你有一组已按照降序排列的数字(例如`List<Integer>`或`ArrayList<Integer>`),并且需要插入一个新数并保持原有的顺序,你可以通过二分查找法快速定位插入位置,然后适当调整列表元素。
以下是基本步骤:
1. 首先,我们需要一个函数`binarySearch`来进行二分查找。这个函数接受一个有序列表、目标值以及列表的开始和结束下标作为参数,返回目标值应该插入的位置,使得列表仍然保持有序。
```java
public int binarySearch(List<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (list.get(mid) > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
```
2. 接着,在主程序中,获取用户输入的新数值`newNum`,调用`binarySearch`函数,然后将新数值插入到正确的位置。由于列表是从大到小排序,所以找到的位置是插入点减一。
```java
int newNum = ...; // 用户输入的新数值
int insertionIndex = binarySearch(sortedList, newNum);
sortedList.add(insertionIndex, newNum); // 注意:add方法会改变列表大小,所以添加前应确保空间可用
System.out.println("新数应在第 " + (insertionIndex + 1) + " 位");
```
这里的`insertionIndex`就是新数应当插入的位置,因为列表是从0开始计数的。
阅读全文