Java使用插入排序对给定数组从小到大排序,不需要输出排序后的数组,需输出从第二个元素开始每个元素 插入的的位置。
时间: 2024-03-14 15:45:36 浏览: 21
以下是Java代码实现:
```java
public class InsertionSortDemo {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
System.out.println("第" + i + "个元素插入的位置是:" + (j + 2));
}
}
}
```
这里使用了插入排序算法,对给定数组从小到大进行排序,并输出每个元素插入的位置。在排序过程中,我们将数组分成了已排序和未排序两部分,每次从未排序的部分取出一个元素,插入到已排序的部分中,使得已排序部分仍然有序。在插入的过程中,我们使用了一个循环来找到插入位置,找到插入位置后,我们将插入位置后面的元素都往后移动一位,然后将待插入元素插入到该位置即可。
相关问题
使用Java使用插入排序对给定数组从小到大排序,不需要输出排序后的数组,需输出从第二个元素开始每个元素 插入的的位置
以下是使用插入排序对给定数组从小到大排序的Java代码,同时输出每个元素在排序过程中插入的位置:
```java
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 将arr[i]插入到已排序区间的合适位置
int j = i;
while (j > 0 && arr[j] < arr[j-1]) {
swap(arr, j, j-1);
j--;
}
// 输出插入的位置
System.out.println(j);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
insertionSort(arr);
```
输出为:
```
1
0
2
1
4
5
2
7
6
3
8
```
其中,第一个元素插入位置为0,表示它已经是已排序区间中最小的元素,不需要插入。从第二个元素开始,每个元素插入的位置即为在已排序区间中找到的第一个比它大的元素的位置。
使用插入排序对给定数组从小到大排序,不需要输出排序后的数组,需输出从第二个元素开始每个元素 插入的的位置JAVA
好的,以下是使用插入排序对给定数组从小到大排序,并输出每个元素插入的位置的JAVA代码:
```java
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
System.out.println("第" + i + "个元素插入的位置为:" + (j + 1));
}
}
```
使用方法:
```java
int[] arr = {5, 3, 8, 1, 9};
insertionSort(arr);
```
输出:
```
第2个元素插入的位置为:0
第3个元素插入的位置为:2
第4个元素插入的位置为:0
第5个元素插入的位置为:4
```
在输出中,第 i 个元素插入的位置为 j,表示在排序后的数组中,原数组的第 i 个元素插入到了排序后数组的第 j 个位置。