欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PHP] 算法-快速排序的PHP实现

程序员文章站 2022-08-28 11:07:00
快速排序: 1.基于二分的思想 2.第一个作为基准数,左右各一个指针,同时扫描,右边先走,找到比基准数小的停下 左边再走,找到比基准数大的停下,左右交换 3.当左右相遇的时候,把当前的和基准数调换,递归调用 4.快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(Nlo... ......
快速排序:
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);