iOS算法系列(3)

<h1>插入排序</h1>
插入排序是构建有序序列,然后把无序的插入有序相应位置形成新的有序序列,周而复始,全部有序.
下面就用代码给大家展示一下.


for(var i=1;i<arr.length;i++){
var arr[i]=key;
var j=i-1;
while(j>=0&&arr[j]>arr[i]){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;

}
最好情况:T(n)=O(n);
最差情况:T(n)=O(n2);
平均情况:T(n)=O(n2);
空间复杂度:O(1).