ソートアルゴリズム

2793 ワード

    :  <  <  <  
 
4:    

/**
 *       ,               ,        ,    
 * @param array $seq
 * @return array
 */
function quicksort($seq) {
    if (count($seq) > 1) {
        $k = $seq[0];
        $x = array();
        $y = array();
        $_size = count($seq);      //do not use count($seq) in loop for.
        for ($i=1; $i<$_size; $i++) {
            if ($seq[$i] <= $k) {
                $x[] = $seq[$i];
            } else {
                $y[] = $seq[$i];
            }
        }
        $x = quicksort($x);
        $y = quicksort($y);
        return array_merge($x, array($k), $y);
    } else {
        return $seq;
    }
}
 
3:    
 
$arr = array(3,2,1);
//              ,           
function insert_sort(&$arr)
{
    //      0         
    for($i=1;$i<count($arr);$i++)
    {
        //$insertValue        
        $insertValue = $arr[$i];
        //    $insertIndex  
        $inserIndex = $i-1;
        
        //        ,             、
        
        while($inserIndex>=0 && $insertValue<$arr[$inserIndex])
        {
            //           
            $arr[$inserIndex+1] = $arr[$inserIndex];
            $inserIndex--;
        }
        
        //  (    $insertValue       )
        $arr[$inserIndex+1] = $insertValue;//   +1     $inserIndex         ,           
    }
}

insert_sort($arr);

print_r($arr);
2:    
$arr = array(1,2,3);
/**
 *              ,        ,      
 * 
 */
function select_sort(&$arr)
{
    $nums = count($arr)-1;//      
    $temp = 0;//          
    for($i=0;$i<$nums;$i++)
    {
        $minValue = $arr[$i];//  $i     
        $minIndex = $i;     //            
        //     ,          
        for($j=$i+1;$j<$nums;$j++)
        {
            if($minValue>$arr[$j])
            {
                $minIndex = $j;
                $minValue = $arr[$j];
            }
        }
        
        //    
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
}

select_sort($arr);
print_r($arr); 
 
 
1.    
 
$arr = array(3,2,1);
//               ,    ,              

function bubble_sort(&$arr)
{
   $flag = false;

   $nums = count($arr)-1;//      $temp = 0;//      
   for($i=0;$i<$nums;$i++)
    {
        //     ,          
        for($j=0;$j<$nums-$i;$j++)
        {
            if($arr[$j]>$arr[$j+1])
            {
                //    
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;

                $flag = true;//            ,       ,          ,       
            }
        }

        if(!$flag){
            //     
            break;
        }else{
            $flag = false;
        }

    }
}

bubble_sort($arr);

print_r($arr);