PHP多叉堆排序和最佳排序选择

1、多叉堆排序和最佳排序选择 MK,每次调整堆平均操作次数是 M*K/2,MKM*M=N（M:叉数 N:元素个数）时效率是最高的。多叉堆排序代码：/*$arr 待排数组$queen 差数*/function maxHeapSort($arr,$queen)/第一步 构建大顶堆maxInitMaxTopHeap($arr,$queen);/第二步 将堆顶和堆尾逐个交换,新的堆顶必将在其子节点产生,所以从堆尾向前成倒序排列$len = count($arr)-1; for($i=$len;$i=0;$i-)$tmp = $arr$i;$arr$i = $arr0;$arr0 = $tmp; maxFo

2、rkOrder($arr,0,$i,$queen);return $arr;/构建大顶堆完全三叉树 子树节点值小于父节点值function maxInitMaxTopHeap(&$arr,$queen)/M 叉树规则 假设有 N 个元素/那么就有 ceil(N/M) 棵树 即最后一棵树的索引是 ceil(N/M)-1/从最后一颗子树开始处理,把更大的值放在父节点上,直到树的顶端比较完,将最大的值放在树顶$start = ceil(count($arr)/$queen)-1;$end = count($arr)-1; for($start;$start=0;$start-)maxForkOrde

3、r($arr,$start,$end,$queen);return $arr;/*二叉树级联梳理 梳理成完全二叉树$start 开始处理的索引$end结束处理的索引$queen 叉 数*/function maxForkOrder(&$arr,$start,$end,$queen)$children = array(); for($i=0;$i $val)/如果有树if($val = $maxIndex & $val $arr$maxValIndex)$maxValIndex = $val;if($maxValIndex != $start)$temp = $arr$start;$arr$st

4、art = $arr$maxValIndex;$arr$maxValIndex = $temp; maxForkOrder($arr,$maxValIndex,$end,$queen);我测试 2500快速排序:0.040421 秒45 叉排序:1.051701 秒30TPHP快速排序，如果数据很小那就使用插入排序(插入排序没有使用函数小数据排序最佳选择，快速排序使用了递归函数，函数和数据一样是放在内存中的，操作效率是低于操作普通数据的后文会提供代码）。如果 数据大到超出内存阈值怎么办呢，那就把数组分成多块，然后每块使用快速排序吧。/快速排序functionfastSort($arr)if(count($arr) 1)$mid = array_shift($arr);$min = array();$max = array(); foreach($arr AS $val)if($val $mid)$min = $val;else$max =$val;$min =fastSort($min);$max =fastSort($max);return array_merge($min,array($mid),$max);elsereturn $arr;/插入排序function insertSort($arr)$len = count($arr); for($i=1;