Java中插入排序实现
时间: 2023-07-03 17:12:55 浏览: 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;
// Move elements of arr[0..i-1], that are
// greater than key, to one position ahead
// of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
```
该算法的时间复杂度为O(n^2),其中n为待排序数组的长度。
相关问题
java中插入排序
Java 中插入排序的实现方式与其他语言类似,也是基于比较和交换元素的思路。以下是 Java 实现插入排序的示例代码:
```java
public class InsertionSort {
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;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
```
在这个示例代码中,`arr` 是待排序的一维数组。`insertionSort` 函数实现了插入排序的算法。该算法使用了一个 `key` 变量来保存当前待排序的元素,然后在已排序的序列中从后往前扫描,找到相应的位置并插入。
java实现插入排序
插入排序是一种简单的排序算法。它的基本思想是,将一个待排序的序列分为两部分,一部分是已排好序的,另一部分是未排序的。每次从未排序的部分取出一个元素,将它插入到已排序部分的适当位置。
Java实现插入排序的代码如下:
```
public static void insertionSort(int[] arr) {
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;
}
}
```
上面的代码使用了两重循环,外层循环枚举未排序部分的元素,内层循环在已排序部分中找到适当的位置并进行插入。
这段代码的时间复杂度为O(n^2),空间复杂度为O(1)。