快速排序说明
- 取一个基数,比它大的放右边,比它小的放左边。
- 2.然后分别对取出的left 和 right 再做排序(递归)也是按照取一个计数,按照比它大的放右边,比它小的放左边。
- 3.合并left,basic right 的值,最后使整个序列有序。
无重复值快速排序
function quickSort($arr){
$length = count($arr);
if($length <=1){
return $arr;
}
$basic = $arr[0];
$left = [];
$right = [];
for($i=0;$i < $length;$i++){
if($arr[$i] < $basic){
$left[] = $arr[$i];
}
if($arr[$i] > $basic){
$right[] = $arr[$i];
}
}
## 针对Left 递归来说~~~每次递归都会执行一次相同的运--即取一个基数,比它大的放右边,比它小的放左边。最后剩下1个值就没必要比较了,然后依次return 返回合并的数组,直到返回给最外层为止。
$left = quickSort($left);
$left[] = $basic;
$right = quickSort($right);
return array_merge($left,$right);
}
$arr = [23,38,22,45,23,67,31,15,41];
print_r(quickSort($arr));
有重复值的快速排序
function quickSort2($arr)
{
$length = count($arr);
if(count($arr) <= 1){
return $arr;
}
$basic = $arr[0];
/*
在此处截取basixc元素 而不是在循环中判断的原因是: 原数组中如果有重复的值的话,循环中的判断会导致重复值
只会出现一次。
###如下写法会导致重复值出现一次
if($basic > $arr[$i]){
$leftArr[] = $arr[$i];
}
if($basic < $arr[$i]){
$rightArr[] = $arr[$i];
}
*/
array_splice($arr,0,1);
$leftArr = [];
$rightArr = [];
for($i=0;$i < count($arr);$i++){
if($basic > $arr[$i]){
$leftArr[] = $arr[$i];
}else{
$rightArr[] = $arr[$i];
}
}
$leftArr = quickSort($leftArr);
$leftArr[] = $basic;
$rightArr = quickSort($rightArr);
return array_merge($leftArr,$rightArr);
}
$arr = [22,38,22,45,23,67,31,15,41];
print_r(quickSort2($arr));
借鉴 http://harttle.land/2015/09/27/quick-sort.html
评论前必须登录!
注册