【排序算法】3.插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

java实现：

public class InsertionOrderTest {
    public static void main(String[] args) {
        int[] input = new int[]{2,5,4,89,7,89,52,12,54,78};
        for (int n = 1; n < input.length; n++){
            int temp = input[n];
            for (int m = n-1 ; m >= 0; m--){
                //如果大于temp，就向后移动一位
                if (input[m] > temp){
                    input[m+1] = input[m];
                }
                //否则就将temp放置在m的上一位
                else {
                    input[m+1] = temp;
                    break;
                }
            }
        }
        PrintUtils.print(input);
    }
}

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

插入算法的问题，是当较小的数据排在后端，向前移动的过程中，就需要不断地把大于它元素向后移。希尔算法就是插入算法的升级版。