Java函数-如何实现插入排序？

插入排序是一种简单直观的排序算法，它的思想是将一个待排序的数依次插入到已经排好序的数列中的合适位置，从而得到一个新的有序数列。

实现插入排序的关键是确定每个待插入的数在已排序数列中的位置。具体步骤如下：

1. 遍历待排序数列，从第二个元素开始（假设 个元素已经有序），依次将当前元素插入到已经排序的序列中。

2. 将当前元素与已排序序列中的元素逐个比较，如果当前元素小于已排序序列中的元素，则将已排序序列中的元素后移一位，直到找到合适的位置插入当前元素。

3. 将当前元素插入到找到的合适位置，完成一次插入操作。

4. 重复步骤2和步骤3，直到遍历完所有待排序元素。

下面给出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--;
            }
            
            // 将当前元素插入到合适的位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 9, 1, 3};
        insertionSort(arr);
        
        // 打印排序后的结果
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

以上代码实现了一个插入排序算法。首先定义了一个insertionSort函数，它接受一个整数数组作为输入，并按照插入排序的思想对数组进行排序。然后在main函数中定义了一个整数数组并调用insertionSort函数对其进行排序，并打印排序后的结果。

输入数组为{5, 2, 8, 9, 1, 3}，经过插入排序后，输出结果为1 2 3 5 8 9。表明插入排序算法成功对输入数组进行了排序。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。尽管插入排序的时间复杂度较高，但在待排序元素基本有序的情况下，插入排序具有较好的性能。