当前位置:  首页>> 技术小册>> Java面试指南

当需要对一组数据进行排序时,我们可以使用插入排序算法。插入排序的基本思想是将一组数据分成已排序部分和未排序部分,然后逐步将未排序部分的数据插入到已排序部分中,直到全部数据有序。下面是一个用Java实现的插入排序算法:

  1. public class InsertionSort {
  2. public static void insertionSort(int[] arr) {
  3. int n = arr.length;
  4. for (int i = 1; i < n; ++i) {
  5. int key = arr[i];
  6. int j = i - 1;
  7. while (j >= 0 && arr[j] > key) {
  8. arr[j + 1] = arr[j];
  9. j = j - 1;
  10. }
  11. arr[j + 1] = key;
  12. }
  13. }
  14. public static void main(String[] args) {
  15. int[] arr = { 12, 11, 13, 5, 6 };
  16. insertionSort(arr);
  17. System.out.println(Arrays.toString(arr));
  18. }
  19. }

这个实现中,我们首先定义一个 insertionSort 方法,该方法接收一个整数类型的数组作为参数。然后,我们遍历整个数组,对于每一个未排序的元素,将其插入到已排序部分的合适位置中。在内部循环中,我们使用 while 循环来将比当前元素大的已排序元素向右移动,以便为当前元素腾出空间。最后,我们将当前元素插入到正确的位置中。

在 main 方法中,我们创建了一个整数数组 arr 并对其进行排序。我们使用 Java 的 Arrays.toString() 方法打印排序后的数组。

该算法的时间复杂度为 $O(n^2)$,其中 $n$ 是数组的大小。如果数组已经部分排序,插入排序算法的时间复杂度可以降低到 $O(n)$。


该分类下的相关小册推荐: