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

while arr[j]>=temp && i

j--

while arr[i]<=temp && i

i++

t=arr[i]

a[i]=arr[j]

a[j]=t;

arr[left]=arr[i]

arr[i]=temp

quickSort(arr,i-1)

quickSort(arr,i+1,right)

//快速排序

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,$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,$right);

var_dump($arr);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!