PHP数据结构(十八)——直接插入排序
(原创内容,转载请注明来源,谢谢)
一、概述
插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半插入排序、2-路插入排序。
二、直接插入排序
直接插入排序是一种最简单的排序方法,时间复杂度O(n2),实现方式是将一个记录插入到已经排序好的有序表,得到一个新的、记录数增加1的有序表。
插入排序的核心思想,即假设原数组的第0位至第i-1位都是有序排列的(如从小到大),当第i位出现顺序错误(如第i位的值小于第i-1位),则需要进行插入排序。
1、算法
直接插入排序经过以下几步:
1)按照待排序数组的顺序,从第二个数字开始,逐个数字与前一个数字进行比较。
2)假设当前的比较是从小到大的排序,数组arr。当arr[i]>=arr[i-1]时,第i个元素保持原位,对i+1进行比较。
3)当arr[i]<arr[i-1]时,则需要进行插入排序。方法是将arr[i]拎出来,从i-1直至0位置的值,逐个进行比较,当比较到第k位,arr[k]<arr[i]时,将arr[k+1]至arr[i-1]的至分别往后挪一位,挪到arr[k+2]至arr[i]的位置,然后将原来的arr[i]的值插入至arr[k+1]处。再继续往后进行比较。
4)直至遍历完所有的节点,插入排序结束,所得的数组即排序好的数组。
5)当需要从大到小排序时,结果相似,不赘述。
2、关键代码实现如下
//直接插入排序
publicfunction directInsertSort(array $arr = array()){
//如果没有输入,则拿默认的值比较
if(empty($arr)){
$arr= $this->arr;
}
//如果数组为空或者只有一个元素,直接返回原数组
if(null== $arr || 1 >= count($arr)){
return$arr;
}
//0...i-1都是有序的,此时插入第i个值
for($i=1;$i<count($arr);$i++){
//当第i个小于第i-1个时,需要进行插入排序,否则循环下一个数
if($arr[$i]< $arr[$i-1]){
//把第i个值往前挪到x位置,保证arr[x-1]<=arr[i],arr[x+1]>arr[i]
$tmp= $arr[$i];
for($j=$i-1;$j>=0&&$arr[$j]>$tmp;$j--){
$arr[$j+1]= $arr[$j];//所有元素往后挪一位
}
//第j+1位赋值留给原来的第i位
$arr[$j+1]= $tmp;
}
}
return$arr;
}
注:此代码为实现直接插入排序的核心代码,代码的方法写在类中,待全部排序都写完后会有完整版的代码
——written by linhxx 2017.07.16
相关阅读: