插入排序算法的基本思路：对于给定的数组a[0...n]（数组元素为n，下标从0开始，最大值为n-1），逐个地将后续元素插入到已经排好序的数组中。

　　插入排序的简单实现如下：

 1 /* 2  * 插入排序算法 3  * a:带排序的数组；n:数组中元素的个数 4  */ 5 void insertSort ( int * a, int n ) { 6     int temp = 0; 7     int i = 0; 8     int j = 0; 9     for ( i = 1; i < n; i++ ) {10         temp = a[i];11         j = i - 1;12         while ( j >= 0 && a[j] > temp ) {13             a[j+1] = a[j];14             j--;15         }16         a[j+1] = temp;17     }18 }

　　 为了做详细的执行步数分析，作如下假设：

　　　　1.c为时钟周期；

　　　　2.所有赋值语句的执行时间都是x1*c；

　　　　3.所有加减法的执行时间都是x2*c;（自增和自减运算作为加减法运算处理）

　　　　4.所有乘除法的执行时间都是x3*c;

　　　　5.所有比较运算的执行时间都是x4*c。

　　执行步骤：

　　　　1.第6、7、8行都只执行一次，总时间为

T1 = 3*x1*c

　　　　2.第9行，i从1自增到n，一共执行n次。i为1时是一次赋值，一次比较；i为其它值时，执行一次加法运算和一次比较运算。故总时间是

T2 = x1*c + n*x4*c + (n-1)*x2*c

　　　　3.第10、11行，只有在当i属于[1,n-1]的集合时，两条语句才会执行，所以这两条语句的总时间是

T3 = (n-1)*x1*c + (n-1)*x2*c

　　　　4.第12行，在for语句的循环体中，i的取值范围是[1,n-1]，而j=i-1，故j的取值范围是[0,n-2]。在最坏情况下（即a[j]>temp总是成立的），对于每个j，while语句每次会执行j+2次（分别是j,j-1,……,0,-1），其中前j+1次（j分别为j,j-1,……,0），两条比较语句都会执行；当j为-1时，只会执行j>=0的比较语句。故在最坏情况下，while语句的执行时间是

　　　　5.第13、14行，有上诉分析可知，最坏情况下对于每个j，while语句会执行j+2次，但由于最后一次不成立，故while循环体中的语句只会执行j+1次，所以13、14行的总时间为

　　　　6.第16行，for语句一共循环n次，但循环体中的语句只执行n-1次，故第16行的总时间为

T6 = (n-1)*x1*c

　　综上所述，插入排序算法最坏情况下的总时间为

　　算法性能往往考虑在输入规模很大的条件下的渐进上界，因此T=O(n²)。实际上，系数项和低次项都没有在最终的结果中体现出来。

　　由于系数项的影响没有体现在算法时间复杂度的最终估计中，因此，就本例而言，x1、x2、x3、x4可以看做是相同的，即对于赋值运算、四则运算和比较运算，我们都可以认为他们的运行时间是单位1，甚至对于循环语句的非循环体（如：本例中的第9行、12行）也可以认为执行一次的时间是单位1，同理对于几条连续的单条语句（如：第6、7、8行，第10、11行，第13、14行）也可以将它们作为一条语句来考虑。

　　进一步，对于低次项，当有简单语句和循环语句一起出现时，如果循环语句确实有执行循环的过程，则简单语句的执行时间可以不用考虑。

　　所以在一般的算法时间复杂度分析中，对循环、循环的嵌套进行分析就可以了。

插入排序算法执行步数浅析