php快速排序

1.数据结构

   //调用
    $test_array = array (12, 5, 10, 9, 100, - 10 );
    $listarray = array ();
    $sort_array = testsort ( $test_array, 2, 0, 5 );
   
    function testsort($array, $index, $begin, $end) {
        global $listarray;
        $listarray = $array;
        if ($begin < $end) {
            $index = quicksort2 ( $listarray, $index, $begin, $end );
            echo 'left<br>';
            testsort ( $listarray, 0, $begin, $index - 1 );
            echo 'right<br>';
            testsort ( $listarray, $index + 1, $index + 1, $end );
        }
        return $listarray;
    }

   //快速排序（快速检索为数组第一个）
    function quicksort1($array, $begin, $end) {
        //echo '<br>输入';
        //print_r($array);
        global $listarray;
        $compare = $array [$begin];
        while ( $begin < $end ) {
            while ( $begin < $end && $array [$end] >= $compare )
                $end --;
            $array [$begin] = $array [$end];
            while ( $begin < $end && $array [$begin] <= $compare )
                $begin ++;
            $array [$end] = $array [$begin];
        }
        $array [$begin] = $compare;
        //echo '<br>输出';
        //print_r($array);
        $listarray = $array;
        return $begin;
    }
   
   
    //快速排序（检索样本为数组第f_index个）
    function quicksort2($array, $f_index, $begin, $end) {
        global $listarray;
        $compare = $array [$f_index];
        while ( $begin < $end ) {
            while ( $begin < $end && $array [$end] >= $compare )
                $end --;
            $array [$f_index] = $array [$end];
            $f_index = $end;
            while ( $begin < $end && $array [$begin] <= $compare )
                $begin ++;
            $array [$f_index] = $array [$begin];
            $f_index = $begin;
        }
        $array [$f_index] = $compare;
        $listarray = $array;
        return $f_index;
    }

   $test_array = array (12, 5, 10, 9, 100, - 10 );
   $sort_array = testsort ( $test_array, 2, 0, 5 );

//快速排序（数组方式）
    function quicksort($array) {
        $count = count ( $array );
        if ($count <= 1)
            return $array;
        $key = $array [0];
        $left_array = array ();
        $middle_array = array ();
        $right_array = array ();
       
        foreach ( $array as $each ) {
            if ($key > $each) {
                //入栈
                array_push ( $left_array, $each );
            } else if ($key == $each) {
                //直接插入
                $middle_array [] = $each;
            } else {
                $right_array [] = $each;
            }
        }
        $left_array = quicksort ( $left_array );
        $right_array = quicksort ( $right_array );
       
        $array = array_merge ( $left_array, $middle_array, $right_array );
        return $array;
    }