当需要对一组数据进行排序时,我们可以使用插入排序算法。插入排序的基本思想是将一组数据分成已排序部分和未排序部分,然后逐步将未排序部分的数据插入到已排序部分中,直到全部数据有序。下面是一个用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;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = { 12, 11, 13, 5, 6 };
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
在
这个实现中,我们首先定义一个 insertionSort 方法,该方法接收一个整数类型的数组作为参数。然后,我们遍历整个数组,对于每一个未排序的元素,将其插入到已排序部分的合适位置中。在内部循环中,我们使用 while 循环来将比当前元素大的已排序元素向右移动,以便为当前元素腾出空间。最后,我们将当前元素插入到正确的位置中。
在 main 方法中,我们创建了一个整数数组 arr 并对其进行排序。我们使用 Java 的 Arrays.toString() 方法打印排序后的数组。
该算法的时间复杂度为 $O(n^2)$,其中 $n$ 是数组的大小。如果数组已经部分排序,插入排序算法的时间复杂度可以降低到 $O(n)$。