[PHP] 算法-快速排序的PHP实现php排序算法
快速排序:
1.基于二分的思想
2.第一个作为基准数,左右各一个指针,同时扫描,右边先走,找到比基准数小的停下
左边再走,找到比基准数大的停下,左右交换
3.当左右相遇的时候,把当前的和基准数调换,递归调用
4.快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)
quickSort &arr,left,right
if left>right return
temp=arr[left]
i=left
j=right
while i<j
while arr[j]>=temp && i<j
j--
while arr[i]<=temp && i<j
i++
t=arr[i]
a[i]=arr[j]
a[j]=t;
arr[left]=arr[i]
arr[i]=temp
quickSort(arr,left,i-1)
quickSort(arr,i+1,right)
<?php
//快速排序
function quickSort(&$arr,$left,$right){
//left大于right的就退出
if($left>$right) return;
//选第一个为基准数
$temp=$arr[$left];
//i是左边的指针
$i=$left;
//j是右边的指针
$j=$right;
//i小于j的时候一直循环
while($i<$j){
//j从右往左走,大于等于基准数就往前走一步,并且最终j会等于i
while($arr[$j]>=$temp && $i<$j){
$j--;
}
//i从左往右走,小于等于基准数的就往前走一步,最终i会等于j
while($arr[$i]<=$temp && $i<$j){
$i++;
}
//调换i和j所在的数
$t=$arr[$i];
$arr[$i]=$arr[$j];
$arr[$j]=$t;
}
//基准数和i,j所在的位置的数调换位置
$arr[$left]=$arr[$i];
$arr[$i]=$temp;
//左半部分递归
quickSort($arr,$left,$i-1);
//右半部分递归
quickSort($arr,$i+1,$right);
}
$arr=array(9,3,5,1,7,9,6,2,4,8,0);
$right=count($arr)-1;
quickSort($arr,0,$right);
var_dump($arr);