插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
算法描述:
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
1.从第一个元素开始,该元素可以认为已经被排序; 2.取出下一个元素,在已经排序的元素序列中从后向前扫描; 3.如果该元素(已排序)大于新元素,将该元素移到下一位置; 4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置; 5.将新元素插入到该位置后; 6.重复步骤2~5。
动图演示:
代码实现:
function insertSort($arr) { $len=count($arr); //1. 确定要插入多少回(假设一个数组一次性插入到对的位置,同时第一个位置是假设对的) for($i=1; $i < $len; $i++) { //2. 取出当前要插入的元素的值 $tmp = $arr[$i]; //3. 内层循环控制,比较并插入----让该数据与前面已经排好序的数组元素重复比较(挨个比较), for($j=$i-1; $j>=0; $j--) { //4. 比较 if($tmp < $arr[$j]) { //发现插入的元素要小,交换位置,将后边的元素与前面的元素互换 $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; } else { // 如果碰到不需要移动的元素,由于是已经排序好是数组,则前面的就不需要再次比较了。 // 说明当前带插入元素,比前面的元素要大:说明位置正确 break; } } } return $arr; }
维基百科:https://en.wikipedia.org/wiki/Insertion_sort
本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn