插入排序:


时间复杂度O(n^2)


代码很短,解释一下,l是要排序的部分的最左一位,r是最右一位,为了方便理解,这里l=1,r=10。
插入排序的主要思想是每次往已经有序的序列中插入一个数,这里可以把i左边的看成已经有序的,i右边的看为正在排序的序列,第i位即是当前所需插入的数。
我们逐句分析:i设定为1+1,也就是第二位,重复执行直到i>10。
这里可以看成for(int i=1+1;i<=10;i++)也就是从第2位扫到第10位。
然后j设定为1,重复执行知道j>i-1也就是从第1位扫到第i-1位,直到找到一个比当前需要插入的数还要大的数,将数插入。
假设有一个序列{1,3,5,2,8,4,9,6,10,7}
我们来模拟一下原程序。
{1,3,5,2,8,4,9,6,10,7}
------i----------------------------------------
{1,3,5,2,8,4,9,6,10,7}
-----------i-----------------------------------
{1,3,5,2,8,4,9,6,10,7}
----------------i------------------------------
{1,2,3,5,8,4,9,6,10,7}
--------------------i--------------------------
{1,2,3,5,8,4,9,6,10,7}
-------------------------i---------------------
{1,2,3,4,5,8,9,6,10,7}
------------------------------i----------------
{1,2,3,4,5,8,9,6,10,7}
----------------------------------i------------
{1,2,3,4,5,6,8,9,10,7}
----------------------------------------i------
{1,2,3,4,5,6,8,9,10,7}
---------------------------------------------i-
{1,2,3,4,5,6,7,8,9,10}
-----------------------------------------------i 这时i>10跳出循环。
插入排序是一种很容易理解的排序,但是速度较慢。