[数据结构与算法]【21天学习挑战赛】算法——插入排序

活动地址：CSDN21天学习挑战赛

插入排序思路

插入排序是基于局部有序进行的，局部有序就是先把一部分数据排序，然后在剩余未排序的数据中取出一个插入到已经拍好序的数据序列中。
在插入排序中选择第一个，作为已经排好序的数据，然后从剩下的未排序的数据中取出一个，与已经排好序的数据逐一比较，如果比其中一个小就差在那个数据前面，以此类推。直到最后一个数据。

插入排序的过程

第一次：把2作为已经排好序的片段，第一次就是排序15
第二次：排序31，由于31，比前两个数据都大因此位置不变
第三次：排序24，经比较，比31小，因此排到31前面
第四次：排序20，经比较，比24小，因此排到24前面
第五次：排序6，经比较，比15小因此排到15前面

插入排序代码

function insertSort(arr){
	let length = arr.length;
	// 外层循环从第一个开始获取数据，向前面局部有序进行插入
  for(let i = 1; i < length; i++){
    let j = i;
    while(arr[j - 1] > arr[j] && j > 0) {
      let temp = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = temp;
      j--;
    }
  }
  return arr;
}

复杂度分析

时间复杂度

最外层循环执行次数：n+1
内层循环执行次数：内层循环作为外层循环的循环体执行n次，但是本身也需要执行n+1次总的执行次数为n(n+1)次
内层循环的语句执行次数：n*n次
因此时间复杂度为O(n2)

空间复杂度

空间复杂度除了输入的数组大小，额外的变量就是用于控制计数的计数器以及临时存储的变量，属于初级别的变量。因此，总的复杂度为O(1);

?