介绍

插入排序是一种简单直观的排序算法，其工作原理类似于人们对扑克牌的排序。

时间复杂度：

• 最好情况：O(n)
• 平均情况：O(n^2)
• 最坏情况：O(n^2)

稳定性：稳定

额外的空间：O(1)

过程

1. 将第一个元素认定为已经被排序
2. 从第二个元素开始，取出元素，将取出的元素由后向前与其前面的元素进行比较
3. 若取出元素小于该元素，则继续向前扫描，直到取出元素小于或等于该元素
4. 将取出元素插在该元素后面
5. 重复步骤2~4直至所有元素排序完成

图示：

宏观过程：

Java实现

/*
 * InsertionSort:插入排序
 */
import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 2, 5, 6, 7, 2, 4, 5};
        System.out.println(Arrays.toString(sort(a)));
    }

    private static int[] sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int b = a[i]; //取出的元素
            int j = i - 1; //往前一位开始搜索
            //将取出元素从右向左进行比较
            while (j >= 0 && a[j] > b) {
                a[j + 1] = a[j]; //向前移位，当该元素小于取出元素时停止移位
                j--;
            }
            a[j+1] = b; //将取出元素插入空位中
        }
        return a;
    }
}