使用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;
            
            // 将比 key 大的元素移动到它后面的位置
            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 = {5, 2, 8, 3, 1};
        insertionSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解析

以上代码是一个使用Java编写的插入排序算法实现。我们通过一个静态方法insertionSort来执行排序操作。该方法接受一个整数数组作为参数，并按升序对该数组进行排序。在insertionSort方法中，我们使用两个嵌套的循环来进行排序：

外部循环从数组的第二个元素开始迭代，直到最后一个元素。这是因为我们将数组的第一个元素视为已排序部分。

内部循环用于将当前元素依次与已排序部分的元素进行比较。如果当前元素小于已排序部分的元素，则将已排序部分的元素向右移动一个位置，并将当前元素插入到正确的位置。内部循环会继续进行，直到当前元素不再小于已排序部分的元素。

通过以上的循环，我们可以确保每一次内部循环结束后，已排序部分的元素都是有序的。最终，整个数组将按升序排序。

总结

本文介绍了如何使用Java编写插入排序算法。通过将未排序的元素逐个插入到已排序部分的正确位置，我们可以快速对小型数组进行排序。插入排序算法的时间复杂度为O(n^2)，适用于小规模数据和接近有序的数组。