写一个插入排序 JAVA
时间: 2023-08-05 21:35:32 浏览: 51
好的,下面是插入排序的 Java 代码实现:
```java
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}
```
这个函数接受一个整型数组作为输入,没有返回值。在函数内部,使用了一个外层循环和一个内层循环来实现插入排序的过程。外层循环用来控制待排序元素的位置,内层循环用来将待排序元素插入到已排序的子数组中正确的位置。
具体来说,我们将数组分成两部分,前面是已排序的子数组,后面是待排序的子数组。外层循环从第二个元素开始,将当前元素作为待排序元素,内层循环从待排序元素的前一个元素开始,向前遍历已排序的子数组,将比待排序元素大的元素向右移动一位,直到找到待排序元素的正确位置,然后将其插入到已排序的子数组中。内层循环结束后,已排序的子数组就扩大了一位,待排序的子数组就缩小了一位。外层循环依次遍历待排序的子数组中的元素,直到所有元素都插入到已排序的子数组中为止。
相关问题
写一个插入排序 java
下面是一个简单的 Java 插入排序的实现:
```java
public class InsertionSort {
public static void main(String[] args) {
int[] arr = { 5, 2, 4, 6, 1, 3 };
insertionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}
}
```
在上面的代码中,我们首先定义了一个 `insertionSort` 函数来实现插入排序。该函数接受一个整数数组 `arr` 作为输入参数。在函数内部,我们首先获取输入数组的长度 `n`。然后,我们从第二个元素开始遍历整个数组。对于第 `i` 个元素,我们将其保存在变量 `key` 中,并将其与前面的所有元素进行比较。如果前面的元素比 `key` 大,则将它们向右移动一位,以便为 `key` 腾出空间。最后,我们将 `key` 插入到合适的位置。通过这个过程,我们可以将整个数组排成一个有序序列。
用Java写一个插入排序
好的,以下是用Java写的插入排序代码:
```java
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 1, 12, -5, 16, 2, 12, 14};
insertionSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
```
在主函数中,我们创建了一个整型数组,并将其传递给`insertionSort`函数进行排序。在`insertionSort`函数中,我们首先获取数组的长度,然后从第二个元素开始遍历数组。对于每个元素,我们将其值存储到`key`变量中,并将其前面的元素与`key`进行比较,如果前面的元素比`key`大,则将其后移一个位置,直到找到一个比`key`小的元素或者遍历到数组的开头为止。最后,我们将`key`插入到正确的位置上。
希望这个代码对你有帮助!