插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。
这里以从小到大排序为例进行讲解。
基本思想及举例说明
插入排序的基本思想是，将元素逐个添加到已经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。
在实际使用中，通常是排序整个无序数组，所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时，将第一个元素作为排序好的子数组，插入第二个元素；第二轮，将前两个元素作为排序好的数组，插入第三个元素。以此类推，第i轮排序时，在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。
下面，以对 3 2 4 1 进行选择排序说明插入过程，使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。
第1轮
[ 3 ] [ 2 4 1 ] （最初状态，将第1个元素分为排序好的子数组，其余为待插入元素） [ 3 ] [ 2 4 1 ] （由于3>2，所以待插入位置j=1） [ 2 3 ] [ 4 1 ] （将2插入到位置j）
第2轮
[ 2 3 ] [ 4 1 ] （第1轮排序结果） [ 2 3 ] [ 4 1 ] （由于2
