插入排序

插入排序是一种简单直观的排序算法。它的基本思想是通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度

在最坏的情况下，插入排序需要O(n^2)的时间复杂度和O(1)的空间复杂度。

空间复杂度

在最好情况下，插入排序需要O(n)的时间复杂度和O(1)的空间复杂度。

Java代码实现

/**
 * 插入排序(Insertion Sort)是一种简单直观的排序算法。
 * 插入排序的工作原理是：通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 
 * 在最好情况下，插入排序的效率为O(n)，对应的序列是已排序的；
 * 在最坏情况下，插入排序的时间复杂度为O(n^2)，对应的序列是逆序的。
 * 
 * 代码的执行步骤：
 * 1. 从第一个元素开始，该元素可以认为已经被排序；
 * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
 * 3. 如果该元素（已排序）大于新元素，将该元素移动到下一位置；
 * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 * 5. 将新元素插入到该位置后；
 * 6. 重复步骤2~5。
 */
public class InsertionSort {
    
    public static void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
}