前言

插入排序是一种稳定的排序算法，和我们打扑克牌时，从桌子上抓牌，然后在手上排序的过程类似。它在性能方面不是最好的，因为要一次构建最终的排序数组。但在传统上比大多数其他简单的O(n 2 )算法（如选择排序或冒泡排序）更有效。也用于混合排序，结合了不同的排序算法来提高性能。

原理

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

因此在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

举个例子，假设有这么几张牌[9,1,3,5,4,2]。 首先拿起第一张牌5，然后拿第二张牌2，把2放在5的左边。然后又拿起一张牌9，把9放在5的右边，以此类推，直到拿起来所有的牌。

这个算法的原理就是把数组分成两个子集，排序子集和未排序子集。最初，排序子集没有元素，每次迭代，插入排序从未排序子集中取出一个元素，并且放置在排序子集相应的位置，在放置时，相当于对给排序子集进行了排序。重复的取出放置，直到未排序子集中没有元素，排序子集中就是已经排好序的数组。

迭代实现

import java.util.Arrays;
 
class Main
{
    public static void insertionSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i  )
        {
            int value = arr[i];
            int j = i;
 
            while (j > 0 && arr[j - 1] > value)
            {
                arr[j] = arr[j - 1];
                j--;
            }
 
            arr[j] = value;
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 9,1,3,5,4,2 };
 
        insertionSort(arr);
 
        System.out.println(Arrays.toString(arr));
    }
}

输出：[1,2,3,4,5,9]

递归实现

import java.util.Arrays;
 
class Main
{
    public static void insertionSort(int[] arr, int i, int n)
    {
        int value = arr[i];
        int j = i;
 
        while (j > 0 && arr[j - 1] > value)
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        arr[j] = value;
 
        if (i   1 <= n) {
            insertionSort(arr, i   1, n);
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 9,1,3,5,4,2 };
        
        insertionSort(arr, 1, arr.length - 1);
 
        System.out.println(Arrays.toString(arr));
    }
}

输出：[1,2,3,4,5,9]

插入排序性能

插入排序的最坏情况时间复杂度是O(n 2 )，其中n是输入的大小。最坏的情况发生在数组反向排序时。插入排序的最佳时间复杂度是O(n)。最好的情况发生在数组已经排序时。因此，插入排序不适合对于数据量比较大的排序应用。

但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知輸入元素大致上按照順序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

迭代版本使用的辅助空间是O(1)，递归版本用于调用堆栈的辅助空间是 O (n)。

这篇好文章是转载于：学新通技术网