JAVA算法起步之插入排序实例

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // 将arr[i]插入到arr[0...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("Sorted array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

这段代码展示了插入排序算法的一个简单实现。插入排序的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。在`main`方法中，我们定义了一个整数数组`arr`，并调用`insertionSort`方法进行排序，最后打印排序后的数组。