# 插入排序（數組排序） ## 定義： > 我們將數組中的數據分為兩個區間，已排序區間和未排序區間。初始已排序區間只有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。  ## 代碼： ~~~ /** * @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. 算法穩定性：元素相等不會交換，是穩定的排序算法 ## 總結 > 插入排序的時間復雜度和冒泡排序一樣，也不是很理想，但是插入排序不涉及數據交換，從更細粒度來區分，性能要略優于冒泡排序。 >