PHP の単純な選択ソートアルゴリズムの例、PHP アルゴリズムの例_PHP チュートリアル-PHPチュートリアル-php.cn

PHP の単純な選択ソートアルゴリズムの例、PHP アルゴリズムの例_PHP チュートリアル

WBOY

リリース： 2016-07-13 10:09:00

オリジナル

995 人が閲覧しました

PHP 単純な選択並べ替えアルゴリズムの例、PHP アルゴリズムの例

シンプルな選択ソートアルゴリズム: キーワード間のn-i比較を通じて、n-i+1レコードから最小のキーワードを持つレコードを選択し、それをi番目(1

コードをコピーしますコードは次のとおりです:

クラスソート{
/**
*簡易選択ソート
*
* @param 不明なタイプ $arr
*/
パブリック関数 selectSort(&$arr) {
$len=count($arr);
for ($i=0;$i<$len;$i++) {
$min=$i;
for ($j=$i+1;$j<=$len-1;$j++) {
If ($arr[$min]>$arr[$j]) {//$arr[$min] より小さい値が見つかった場合、添え字を $min に割り当てます
$min=$j;
}
}
If ($min!=$i){//$min が $i に等しくない場合、最小値が見つかったことを意味し、交換
$this->swap($arr[$i],$arr[$min]);
}
}
}
/**
* 2 つの値 $a と $b の位置を入れ替えます
*/
パブリック関数スワップ(&$a,&$b) {
$temp=$a;
$a=$b;
$b=$temp;
}
}
$arr=array(4,6,1,2,9,8,7,3,5);
$test=新しい並べ替え(); $test->selectSort($arr);//単純な選択ソート
// var_dump($arr);
?>

シンプルな選択ソートの特徴:モバイルデータの交換回数が非常に少ないため、対応する時間を節約できます

単純な選択ソートの時間計算量分析:
最良の場合でも最悪の場合でも、比較の数は同じです。i 番目の並べ替えでは、n-i 個のキーワードの比較が必要です。つまり、n(n-1)/2 個の比較が必要です。したがって、最終的な時間計算量は O(n^2) になります
バブルソートと同様に O(n^2) ですが、それでも選択ソートのパフォーマンスはバブルソートよりわずかに優れています。