【PHP】简单排序算法

冒泡排序

遍历列表，比较两个相邻元素的大小，不符合排序就交换相邻元素的位置，直到遍历结束或没有可交换的元素，则排序完成。
最大的缺点：慢

方式一

#遍历所有元素，每次遍历选出最值
#递减
function bubble_sort_1($arr)
    {
        $len = count($arr);
        for($i=1;$i<$len;$i++){
            for($j=0; $j<$len-$i; $j++){
                if ($arr[$j]<$arr[$j+1]){
                    list($arr[$j],$arr[$j+1]) = [$arr[$j+1],$arr[$j]];
                }
            }
        }
        return $arr;
    }

方式二

#遍历至没有可交换的元素
#递减
function bubble_sort_2($arr)
    {
        $len = count($arr);
        do{
            $swapped = false;
            for ($i=0,$c=$len-1; $i<$c; $i++){
                if ($arr[$i+1]>$arr[$i]){
                    list($arr[$i+1],$arr[$i]) = [$arr[$i],$arr[$i+1]];
                    $swapped = true;
                }
            }
        }while($swapped);
        return $arr;
    }

快速排序

快速排序是比较大小的排序，也就是说只要列表的元素都可比较大小，就能用快速排序。
缺点：可能出现递归次数超过限制：“Maximum function nesting level of '512' reached”，比如，$arr为1～10000递增的数组时

#递减
function quickSort($arr)
    {
        $len = count($arr);
        if ($len<2){
            return $arr;
        }

        $min = $max = $base = [];
        $base_item = $arr[0];
        for ($i=0; $i<$len; $i++){
            if ($arr[$i]<$base_item){
                $min[] = $arr[$i];
            }elseif($arr[$i]>$base_item){
                $max[] = $arr[$i];
            }else{
                $base[] = $arr[$i];
            }
        }
        $min = $this->quickSort($min);
        $max = $this->quickSort($max);
        return array_merge($max,$base,$min);
    }

选择排序

冒泡排序升级版，每次遍历最多只交换一次元素位置

#递减
function selectsort($arr)
    {
        $len = count($arr);
        for ($i=0;$i<$len-1;$i++){
            $max = $i;
            for ($j=$i+1;$j<$len;$j++){
                if ($arr[$j]>$arr[$max]){
                    $max = $j;
                }
            }
            if ($max != $i){
                list($arr[$max],$arr[$i]) = [$arr[$i],$arr[$max]];
            }
        }
        return $arr;
    }

简单对比

对同一个1～10000随机打乱排列的数组，以上方法所需时间

"quick_sort": 56.137939453125,
"bubble_sort_1": 11953.06298828125,
"bubble_sort_2": 18395.77197265625,
"select_sort": 6399.743896484375