插入排序（Insertion Sort）是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

说明：

在插入排序中，我们维护两个指针，一个在已排序的序列中，通常从后向前移动（这是实现的一种方式，也可以从前向后移动），另一个在未排序的序列中，向前移动。当未排序的元素找到在已排序序列中的位置时，它就被插入。

例如，对于数组 [5, 3, 4, 7, 2, 8, 6, 9, 1]，插入排序的过程如下：

1. 我们首先把3插入到已排序的序列 [5] 中，得到 [3, 5]。
2. 然后我们把4插入到已排序的序列 [3, 5] 中，得到 [3, 4, 5]。
3. 接着我们把7插入到已排序的序列 [3, 4, 5] 中，得到 [3, 4, 5, 7]。
4. 然后我们把2插入到已排序的序列 [3, 4, 5, 7] 中，得到 [2, 3, 4, 5, 7]。
5. 最后我们把8和9插入到已排序的序列 [2, 3, 4, 5, 7] 中，得到 [2, 3, 4, 5, 7, 8, 9]。

时间复杂度：

• 最好情况：O(n)，当输入已经部分排序时（这是由于元素不需要移动或移动很短距离）
• 最坏和平均情况：O(n^2)
• 空间复杂度：O(1)（因为只使用了常量级别的额外空间）

用途：

插入排序在以下情况中特别有用：

• 数据量较小，或者数据已经部分排序时。当数据量较大且无序时，插入排序的效率较低。
• 对于部分有序的数据，插入排序的效率较高。
• 当数据是链表或者内存使用效率非常重要的时候。

JAVA代码实例：

import java.util.Arrays;

public class InsertionSort {  
     public static int[] sort(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]; // 如果当前元素（key）比前一个元素小，就将前一个元素向后移动一位  
                j = j - 1;  
            }  
            arr[j + 1] = key; // 将key插入到正确的位置  
        }
        return arr;  
    }  
     public static void main(String args[]) {  
        int arr[] = {64, 34, 25, 12, 22, 11, 90};  
        int[] result = sort(arr);  
        System.out.println("排序结果为：" + Arrays.toString(result));
        // 排序结果为：[11, 12, 22, 25, 34, 64, 90]
    }  
}

这段代码是插入排序的基本实现。sort方法遍历整个数组，对于每个元素，它都在已排序的序列中找到正确的位置并插入。如果当前元素小于已排序序列中的某个元素，就将该元素向后移动一位，直到找到当前元素的正确位置。