PHP二叉树排序的基本实现

Sian

[PHP] 纯文本查看 复制代码

<?php
        
        $array = array(1,42, 11, 93, 2,4,12,41,19,29);
        print_r($array);
        echo "<br/>";
        
        // 定义一个函数来实现二叉树
        function qsort($array){
                // 如果非数组或数组为空则直接返回一个空数组
                if(!is_array($array) || empty($array)) return array();
                // 如果数组长度为1时，直接返回这个数组
                $len = count($array);
                if ($len <= 1) return $array;
                
                // 定义一个变量来设置二叉树的根
                $key[0] = $array[0];
                // 定义一个小数值数组和一个大数值数组
                $left = array();
                $right = array();
                
                // 如果比根小则放左边，如果比根大则放右边
                // 通过循环会将所有的大值都放到右边的数组
                // 所有的小值都放在左边的数组，但无规则
                for($i = 1;$i<$len; $i++){
                        if($array[$i] >= $key[0]){
                                $right[] = $array[$i];
                        }else{
                                $left[] = $array[$i];
                        }
                }
                
                // 通过递归继续循环直到只有一个值时再返回
                // 递归结束后，左边数组为排序好的小值
                // 右边数组为排序好的大值，再拼合成一个数组
                $left = qsort($left);
                $right = qsort($right);
                
                // 返回最终结果
                return array_merge($left, $key, $right);
        }
        
        // 输出排序好之后的数组
        print_r(qsort($array));

输出结果为：
Array ( [0] => 1 [1] => 42 [2] => 11 [3] => 93 [4] => 2 [5] => 4 [6] => 12 [7] => 41 [8] => 19 [9] => 29 )
Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 11 [4] => 12 [5] => 19 [6] => 29 [7] => 41 [8] => 42 [9] => 93 )