PHPにおける各種ソートアルゴリズム(時間複雑度等)
2527 ワード
時間複雑度O(n 2)のアルゴリズム:
ソートを挿入:(ソートする数を取り出してから、その数より大きいものがあるかどうか、移動位置があるかどうか、いいえ、後に進みます)
時間複雑度O(nlogn)のアルゴリズム:
クイックソート(まず参照値を探して、それより小さいものを見つけて1つの配列に分けて、大きいものを見つけて別の配列に分けて、それから順番に探して)ポイントは再帰思想で、再帰が終わるたびに、見つけた配列をソートします.最後に返されるのは秩序ある配列です.
パラメータ
説明
array
必要です.ソートする配列を指定します.
myfunction
オプション.比較関数を呼び出す文字列を定義します.最初のパラメータが2番目のパラメータ以下の場合、比較関数は0以下の整数を返さなければなりません.
ソートを挿入:(ソートする数を取り出してから、その数より大きいものがあるかどうか、移動位置があるかどうか、いいえ、後に進みます)
$n = count($nu);
for($i =1;$i=0 && $temp
バブルソート:(すなわち、大きい数はまっすぐ後ろに並び、n-1回、毎回n-1-i回) $n = count($nu);
for($i=0;$i$nu[$j+1])
{
$tem = $nu[$j];
$nu[$j] = $nu[$j+1];
$nu[$j+1] = $tem;
}
}
}
時間複雑度O(nlogn)のアルゴリズム:
クイックソート(まず参照値を探して、それより小さいものを見つけて1つの配列に分けて、大きいものを見つけて別の配列に分けて、それから順番に探して)ポイントは再帰思想で、再帰が終わるたびに、見つけた配列をソートします.最後に返されるのは秩序ある配列です.
function quickSort(&$arr){
if(count($arr)>1){
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;$i$k){
$y[]=$arr[$i];
}
}
$x=quickSort($x);
$y=quickSort($y);
var_dump($x);
var_dump($y);
var_dump($k);
//var_dump($y);
//var_dump(array_merge($x,array($k),$y));
return array_merge($x,array($k),$y);
}else{
return $arr;
}
}
quickSort($nu);
集計ソート:$arr=array(5,3,2,4,1);
$GLOBALS['res']=0;
function merge_sort(&$arr){
$len=count($arr);
if($len==1)
return $arr;
$middle=intval($len/2);
$left=array_slice($arr,0,$middle);
$right=array_slice($arr,$middle);
merge_sort($left);
merge_sort($right);
$arr=merge($left,$right);
return $GLOBALS['res'];
}
function merge($leftarr,$rightarr){
$arr = array();
static $res = 0;
while(count($leftarr) && count($rightarr))
{
if($leftarr[count($leftarr)-1] > $rightarr[count($rightarr)-1]){
$res = $res+count($rightarr);
$GLOBALS['res'] =$res;
array_unshift($arr,array_pop($leftarr));
}else{
array_unshift($arr,array_pop($rightarr));
}
}
return array_merge($rightarr,$leftarr,$arr);
}
sort関数----usort()カスタム関数を使用して、サイズを比較します.usort(array,myfunction);
パラメータ
説明
array
必要です.ソートする配列を指定します.
myfunction
オプション.比較関数を呼び出す文字列を定義します.最初のパラメータが2番目のパラメータ以下の場合、比較関数は0以下の整数を返さなければなりません.
$numbers = array(3,32,321);
usort($numbers, function($a,$b){
if($a>$b)return 1;
return -1;
// if("$a$b" > "$b$a") return 1;
// return -1;
});
var_dump($numbers);