|
出于这个想法，我们修改 Partition() 函数：
$arr[$high]){
swap($arr,$high);
}
if($arr[$mid] > $arr[$high]){
swap($arr,$mid,$high);
}
if($arr[$low] < $arr[$mid]){
swap($arr,$mid);
}
//经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
$pivot = $arr[$low];
while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。
优化二：优化不必要的交换：
现在假如有个待排序的序列如下：
根据三数取中法我们取 5 7 2 中的 5 作为枢轴。
当你按照快速排序算法走一个循环，你会发现 5 的下标变换顺序是这样的：0 -> 8 -> 2 -> 5 -> 4，但是它的最终目标就是 4 的位置，当中的交换其实是不需要的。
根据这个思想，我们改进我们的 Partition() 函数:
= $pivot){
$high --;
}
//swap($arr,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
$arr[$low] = $arr[$high]; //使用替换而不是交换的方式进行操作
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
//swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
$arr[$high] = $arr[$low];
}
$arr[$low] = $temp; //将枢轴数值替换回 $arr[$low];
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
在上面的改进中，我们使用替换而不是交进行操作，由于在这当中少了多次的数据交换，因此在性能上也是有所提高的。
优化三：优化小数组的排序方案：
对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培育最优秀的数学博士，当让他去教小学生“1 + 1 = 2”的算术课程，那还真未必比常年在小学里耕耘的数学老师教的好。换句话说，大材小用有时会变得反而不好用。
也就是说，快速排序对于比较大数组来说是一个很好的排序方案，但是假如数组非常小，那么快速排序算法反而不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序的时候，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大炮打蚊子的大问题。
因此我们需要修改一下我们的 QSort() 函数：
= $high 时表示不能再进行分组，已经能够得出正确结果了
if(($high - $low) > MAX_LENGTH_INSERT_SORT){
$pivot = Partition($arr,$high); //对高子表（$pivot右边的记录）进行递归排序
}else{
//直接插入排序
InsertSort($arr);
}
}
PS：上面的直接插入排序算法大家可以参考：《》
在这里我们增加一个判断，当 $high - $low 不大于一个常数时（有资料认为 7 比较合适，也有认为 50 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。
优化四：优化递归操作：
（编辑：网站开发网_马鞍山站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
