1 .插入排序概念插入排序的基本方法是，在每个步骤中，将要排序的元素按其排序代码的大小插入到之前排序的元素集中的适当位置，直到插入所有元素。
您可以选择其他方法，在排序的数据表中查找插入位置。 根据搜索方法的不同，有几种插入排序方法，接下来介绍的是直接插入排序。
2 .直接插入排序的基本思想
直接插入中断的基本思路是，插入第I(I=1)眼时，前面的v(0)、v(0)、…、v(I-1 )已经排序。 此时，将V[I]的排序代码与V[i-1]，V[i-2]，…的排序代码的顺序进行比较，找出插入位置插入V[I]，将原来位置的要素向后顺序输送。
图1表示直接插入排序的过程。 假设要素表中有n=6个要素，为了使说明书的概要直观，图中只画了各要素的分类代码。 其中两个排序代码相同，第一个直接写25，第二个写25*。 这里假设V[0]、V[i-1]已经是一组有序的元素，V[i]、V[i 1]、V[n-1]是带插入的元素。 排序过程从i=1开始，每执行一次I增加1，将第I个元素插入到前一个有序的元素阵列中，以确保插入后的元素阵列V[0]、V[1]、V[i-1]保持有序。
图直接插入排序过程
图1(b )是分类过程) i=4)的例子。 此时，从V[0]到V[3]的顺序已经确定，算法首先比较V[4]和V[3]。 由于V[4]V[3]，需要从V[3]到V[0]查找插入位置，为此需要将V[4]临时保存在临时变量temp中，放置上一个元素，然后从后面开始按顺序比较来查找插入位置。 假设循环变量为j，如果V[j]的排序代码大于temp的排序代码，则将V[j]向后移动直到比较了某个V[j]为temp以下的排序代码或要素的排列，最后暂时保存在temp中的原始要素V[i] 算法的源代码：如下所示
3 .排序源templateclasstvoidinsertsort (t * array，int n ) ) { //array待排序数组，n:数组元素数int i，j； //循环变量T temp； //保存排序对象要素for (I=1； i n； I () j=I； temp=array[i]； //排序对象元素未达到临时变量while(j0temparray[j-1] ) /数组中的第一个元素，或者插入对象元素是当前元素array[j]=array[j - 1]； //使其元素为J----； //减少一个下标并继续比较(}array[j]=temp； //找到了插入位置。 立即插入}4.直接插入排序时间复杂度分析假设要排序的元素数为n，则该算法将运行n-1次。 因为排序代码的比较次数和要素的移动次数与要素的排序代码的初始排列有关，所以在最好的情况下，也就是说在排序前要素按照排序代码的大小从小到大的顺序排列的情况下，各趟是否可以与前面的顺序要素排列的最后的要素的排列进行比较，进行总排序代码的比较最差情况以及第I回合的第I个要素必须与上述第I个要素进行排序码的比较，并且每次被调用时必须进行数据移动。 在最坏情况下，排序码的排序码比较次数KCN和要素移动次数RMN分别为：
从上面的讨论中可以看出，直接插入排序的执行时间与排序对象元素的原始排序顺序密切相关。 如果排序对象要素列中出现各种可能的排列的概率相同，则可以取上述最佳和最坏情况的平均，平均情况下的排序代码比较次数和要素移动次数约为n^2/4。 因此，直接插入排序的时间复杂度为o(n^2)。 另外，直接插入排序是一种稳定的排序方法。