# 插入排序（数组排序） ## 定义： > 我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。  ## 代码： ~~~ /** * @param $nums * @return mixed * 4 3 2 1 */ function insert_sort($nums){ if(count($nums) <= 1){ return $nums; } for($i=1;$i<count($nums);$i++){//控制最大循环次数 $value = $nums[$i];//记录下当前需要比较的元素的值 for($j=$i-1;$j>=0;$j--){//拿$value值与已排序区的每个值比较，如果大于$value就后移一位 if($nums[$j] > $value){ $nums[$j+1] = $nums[$j]; }else{ break; } } $nums[$j+1] = $value;//把最后一个后移的值替换成为$value,这样一次循环就完成了 } return $nums; } $nums = [4,3,1,2]; print_r(insert_sort($nums)); ~~~ ## 插入排序的性能和稳定性 1. 时间复杂度： O(n^2) （n的平方） 2. 空间复杂度：没有额外的存储空间，是原地排序算法 3. 算法稳定性：元素相等不会交换，是稳定的排序算法 ## 总结 > 插入排序的时间复杂度和冒泡排序一样，也不是很理想，但是插入排序不涉及数据交换，从更细粒度来区分，性能要略优于冒泡排序。 >