PHPはいくつかの基本的な並べ替えアルゴリズムを実現する--泡の並べ替え法、急速な並べ替え法、選択の並べ替え法、挿入の並べ替え法

前提:それぞれバブルソート法,クイックソート法,ソート法を選択し,挿入ソート法は次の配列の値を小さい順にソートする.  $arr(1,43,54,62,21,66,32,78,36,76,39);  
1.泡立ちソート
構想分析:並べ替える1組の数の中で、現在まだ並べられていないシーケンスに対して、行った後から隣接する2つの数を順番に比較して調整して、大きい数を沈下させて、小さいのは上へ出ます.すなわち、2つの隣接する数が比較された後、それらのソートがソート要件と逆であることが発見されるたびに、それらを交換する.コード実装:$arr=array(1,43,54,62,21,66,32,78,36,76,39);function bubbleSort($arr){$len=count($arr);//この層サイクル制御泡を立てる必要がある輪数for($i=1;$i{//この層サイクルは、各輪から1つの数が出るのに比較する必要がある回数for($k=0;$k{if($arr[$k]>$arr[$k+1]){tmp=$arr[$k+1]){;             $arr[$k+1]=$arr[$k];             $arr[$k]=$tmp;         }     }   }   return $arr; }  
2.ソートの選択
構想分析:ソートする一連の数の中で、最小の数と最初の位置の数を交換することを選択します.そして残りの数の中で最小の2番目の位置との数を交換し、逆数の2番目の数と最後の数を比較するまでループします.コード実装:function selectSort($arr){//二重ループ完了、外層制御ホイール数、内層制御比較回数$len=count($arr);for($i=0;$i//最小値の位置$p=$i;for($j=$i+1;$j//$arr[$p]現在既知の最小値if($arr[$p]>$arr[$j]){//比較であり、より小さいことが判明し、最小値の位置が記録され、次回の比較時に既知の最小値で比較される.$p=$j;}}//現在の最小値の位置が決定され、$pに保存されます.最小値の位置が現在仮定されている位置$iと異なる場合、位置交換が可能である.        if($p != $i) {             $tmp = $arr[$p];             $arr[$p] = $arr[$i];             $arr[$i] = $tmp; }}//最終結果return$arrを返します. 
3.ソートの挿入
構想分析:並べ替える1組の数の中で、前の数がすでに順番に並んでいると仮定して、今n番目の数を前の序数に挿入して、このn番目の数も順番に並べます.このように繰り返して、すべて順番が整うまで.コード実装:function insertSort($arr){$len=count($arr);for($i=1,$i$tmp=$arr[$i];//内層サイクル制御、比較挿入for($j=$i-1;$j>=0;$j--){if($tmp//挿入された要素が小さいことを発見し、交換位置、後の要素を前の要素と$arr[$j+1]=$arr[$j];$arr[$j]=$tmp;}else{//移動を必要としない要素に遭遇し、配列がソートされているため、前の要素を再比較する必要はありません.break;            }         }     }     return $arr; }  
4.クイックソート
構想分析:基準要素を選択し、通常は最初の要素または最後の要素を選択します.1回のスキャンにより、並べ替えられるシーケンスを2つの部分に分け、一部はベース準要素より小さく、一部は基準要素以上である.このとき、基準要素は、順序付け後の正しい位置にあり、分割された2つの部分を同じ方法で再帰的に並べ替える.コード実装:function quickSort($arr){//$length=count($arr);if($length<=1){return$arr;}//最初の要素を基準$base_として選択num = $arr[0];//ルーラー以外のすべての要素を巡り、2つの配列にサイズ関係で入れる//2つの配列を初期化$left_array = array();//基準より小さい$right_array = array();//基準より大きいfor($i=1;$i if($base_num>$arr[$i]){//左配列$left_array[]=$arr[$i];}else{//右の$right_array[]=$arr[$i];}//左と右の配列を同じソート処理で再帰的に呼び出すこの関数$left_array = quick_sort($left_array);     $right_array = quick_sort($right_array);//return arrayのマージmerge($left_array, array($base_num), $right_array); }
 
変換元:http://mp.weixin.qq.com/s?__biz=MzA5Mjg2NTQxOA==&mid=2650420273&idx=1&sn=f2db8b34f560d9d8253af5fb712d172e&scene=4#wechat_redirect

/*
 * php              sort    
 * 3000   ，              
 *      857.98192024231ms
 *      903.74493598938ms
 *      296.8270778656ms
 *      15.607833862305ms
 * sort   0.95200538635254ms
 *      14.61386680603ms
 * */


/*
* @param     
*              ，        ，                 。
*                       ，             。
* */
function BubbleSort($arr) {
    $len = count($arr);
    //                 
    //              
    for ($i = 1; $i < $len; $i++) {
        $flag = false;    //       ，       
        //                        
        for ($k = 0; $k < $len - $i; $k++) {
            //      
            if ($arr[$k] > $arr[$k + 1]) {
                $tmp = $arr[$k + 1];
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $tmp;
                $flag = true;
            }
        }
        if(!$flag) return $arr;
    }
}

/*
* @param      
*                  （   ）     ，          ，              。
*              （    [5， 5， 3]        [5] [3]  ，     5      5  ）
* */
function selectSort($array){
    $temp = 0;
    for($i = 0;$i < count($array) - 1;$i++){
        $minVal = $array[$i]; //  $i     
        $minValIndex = $i;
        for($j = $i+1;$j < count($array);$j++){
            if($minVal > $array[$j]){ //      
                $minVal = $array[$j]; //    
                $minValIndex = $j;
            }
        }
        $temp = $array[$i];
        $array[$i] = $array[$minValIndex];
        $array[$minValIndex] = $temp;
    }
}

/*
*      
*            ，                          ，         。
*             ，      O(n^2)。        。
* */
function insertSort($array){ //      
//   $array[0]，    ，    
    for($i = 1;$i < count($array);$i++){
        $insertVal = $array[$i]; //$insertVal       
        $insertIndex = $i - 1; //             
        while($insertIndex >= 0 && $insertVal < $array[$insertIndex]){
            $array[$insertIndex + 1] = $array[$insertIndex]; //      
            $insertIndex--; //      ，          
        }
        if($insertIndex + 1 !== $i){
            $array[$insertIndex + 1] = $insertVal;
        }
    }
}

/*
*      
*                       ，                         ，
*                       ，            ，              。
* */
function quickSort($array){
    if(!isset($array[1]))  return $array;
    $mid = $array[0]; //            ，       
    $leftArray = array();
    $rightArray = array();
    foreach($array as $v){
        if($v > $mid)
            $rightArray[] = $v; //  $mid          
        if($v < $mid)
            $leftArray[] = $v; //  $mid           
    }
    $leftArray = quickSort($leftArray); //              
    $leftArray[] = $mid; //              ，      
    $rightArray = quickSort($rightArray); //              
    return array_merge($leftArray,$rightArray); //      
}

/*
*     
*                    （    ），            （    ）。
*                                 。
* */
function mergeSort(&$arr) {
    $len = count($arr);//      
    mSort($arr, 0, $len-1);
    return $arr;
}
//           
function mSort(&$arr, $left, $right) {
    if($left < $right) {
        //          1    ，      ，    ，  
        //       ，  /2   
        $center = floor(($left+$right) / 2);
        //             ：
        mSort($arr, $left, $center);
        //             
        mSort($arr, $center+1, $right);
        //      
        mergeArray($arr, $left, $center, $right);
    }
}
//                
function mergeArray(&$arr, $left, $center, $right) {
    //          
    $a_i = $left;
    $b_i = $center+1;
    while($a_i<=$center && $b_i<=$right) {
        //   A   B      
        if($arr[$a_i] < $arr[$b_i]) {
            $temp[] = $arr[$a_i++];
        } else {
            $temp[] = $arr[$b_i++];
        }
    }
    //     A          ，           C   ：
    while($a_i <= $center) {
        $temp[] = $arr[$a_i++];
    }
    //     B          ，           C   ：
    while($b_i <= $right) {
        $temp[] = $arr[$b_i++];
    }

    // $arrC       ，   $arr ：
    for($i=0, $len=count($temp); $i

変換元:http://www.cnblogs.com/jing1208/p/6289840.html