插入排序

插入排序的工作原理是通过构造有序元素序列，对于未排序数据，在已排序元素中从后往前扫描，找到相应位置并插入

插入排序的工作原理是通过构造有序元素序列，对于未排序数据，在已排序元素中从后往前扫描，找到相应位置并插入

算法描述

1. 从第一个元素开始，假设该元素是已被排序
2. 取出下一个元素，在有序元素序列中由后往前扫描比较
3. 如果已排序的元素大于该元素，则把已排序元素向后移一个位置
4. 重复步骤3，直到排序的元素小于或等于该元素
5. 把该元素插入到排序元素位置后
6. 重复步骤2~5

插入排序过程，可参见下图

插入算法最坏时间复杂度O($n^2$)，最优时间复杂度O($n$)，平均时间复杂度（$n^2$） 空间复杂度O($n$)，需要辅助空间O(1)

范例代码

public static void insertion_sort( int[] arr ){
    for( int i=0; i<arr.length-1; i++ ) {	
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

结语

从算法复杂度可以看出，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择