插入排序

  • 平均时间复杂度O(n*n)
  • 最差情况O(n*n)
  • 最好情况O(n)
  • 空间复杂度O(1)
  • 稳定性：稳定
function insertSort (arr) {
 var len = arr.length;
 var temp;
 for (var i = 1;i < len;i++){
 for(var j = i;j > 0 && arr[j] < arr[j-1];j--){
 // 当前值和之前的每个值进行比较，发现有比当前值小的值就进行交换
 temp = arr[j];
 arr[j] = arr[j-1];
 arr[j-1] = temp;
 }
 }
 return arr
}
插入排序的排序效率要比选择排序的高，当排序有一定顺序的数组时，效率会非常高
function insertSort(arr) {
 var len = arr.length;
 var temp;
 for (var i = 1;i < len;i++){
 temp = arr[i];
 for (var j = i;j > 0 && temp < arr[j-1];j--){
 // 当前值和之前的每个值进行比较，发现有比当前值小的值就进行重新赋值
 arr[j] = arr[j-1];
 arr[j-1] = temp;
 }
 }
 return arr;
}
重新赋值比数值交换效率更高一些

最终升级版
function insertSort(arr) {
 var len = arr.length;
 var temp;
 for (var i = 1;i < len;i++){
 temp = arr[i]
 for (var j = i;j > 0 && temp < arr[j-1];j--){
 // 当前值和之前的每个值进行比较，发现有当前值小的值就进行重新赋值
 arr[j] = arr[j-1];
 }
 arr[j] = temp;
 }
 return arr;
}
相比较上一个版本，少了一些中间比较时进行的赋值，只取最终的位置进行赋值
 


 

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

 

 

 

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄