快速排序通常是用于排序的最佳实用选择，虽然最坏情况下时间性能为O(n*n)，但其平均时间性能为O(nlgn)且记号中隐含的常数因子很小，且为原地排序。
快速排序也是一种分治模式，其基本思想如下：找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区（Partition，核心部分）操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置；然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
//Partition PHP实现
function Partition(&$array,$p,$r){
$key=$array[$p];
$i=$p; $j=$r;
while($i<$j){
while($i<$j&&$array[$j]>$key){$j--;}
if($i<$j){$array[$i]=$array[$j]; i++;}
while($i<$j&&$array[$i]<$key){$i++;}
if($i<$j){$array[$j]=$array[$i]; $j--;}
}
$array[$i]=$key;
return $i;
}
//快速排序 PHP实现
function Quick_sort(&$array,$p,$r){
if($p<$r){
$pivot=Partition($array,$p,$r);
Quick_sort($array,$p,$pivot-1);
Quick_sort($array,$pivot+1,$r);
}
}
快速排序的运行时间与划分是否对称有关，而后者又与选择了哪个元素进行划分有关；如果划分是对称的，那么本算法从渐近意义上和合并排序一样快，如果划分不对称，本算法从渐近意义和插入排序一样慢。
//快速排序的随机化版本
Random_Partition(&$array,$p,$r){
$i=rand($p,$r);
swap($array[$i],$array[p]);
return Partition($array,$p,$r);
}
2. 荷兰国旗问题和三路快速排序
问题描述：荷兰国旗有红、白、蓝三种颜色。现有这三种颜色的小球混放在一起，要求对小球排序，使得相同颜色的小球相邻摆放。问题模型化：假设用数字0，1，2代表红、白、蓝三种颜色。数组array混乱存放着这些代表球的颜色的元素值。
//荷兰国旗 PHP实现
function Threeflag(&$array,$p,$r){
$beg=$p; $end=$r; $curr=$p;
while($curr<=$end){
if($array[$curr]==0){
swap($array[$beg],$array[$curr]);
$curr++; $beg++;
}elseif($array[$curr]==2){
swap($array[$end],$array[$curr]);
$end--;
}elseif($array[$curr]==1){
$curr++;
}
}
}
快速排序算法扩展之三路快速排序算法：
随机快排虽然能很大程度上解决子问题划分不均的情况，但当排序对象中有很多重复的元素时，快排划分情况很不尽人意。例如：当所有元素都相等时，在每次递归中，左边部分是空的(没有元素比关键元素小)，而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。为了解决这个问题(有时叫做荷兰国旗问题)，我们将快排划分扩展为三路快排：即排序对象被划分为三部分：<$privot，=$privot，>$privot
//三路快速排序 PHP实现
function quick_sort(&$array,$p,$r){
if ($p<$r) {
$pivot=ThreePartition($array,$p,$r);
quick_sort($array,$p,$pivot[0]);
quick_sort($array,$pivot[1]+1,$r);
// $pivot=Partition($array,$p,$r);
// quick_sort($array,$p,$pivot-1);
// quick_sort($array,$pivot+1,$r);
}
}
//three partition
function ThreePartition(&$array,$p,$r){
$key=$array[$p];
$i=$p; $j=$r; $k=$p;
while ($k<=$j) {
if ($array[$k]<$key) {
swap($array[$i],$array[$k]);
$i++;$k++;
}elseif ($array[$k]>$key) {
swap($array[$j],$array[$k]);
$j--;
}elseif ($array[$k]==$key) {
$k++;
}
}
return array($i,$j);
}
网友评论