PHP ソート アルゴリズム シンプル セレクション ソート (シンプル セレクション ソート)

この記事では、主に PHP ソート アルゴリズムの Simple Selection Sort (Simple Selection Sort) を紹介し、その原理と関連する実装テクニックをサンプルの形式で詳細に分析します。この記事の例では、PHP のソート アルゴリズム Simple Selection Sort を学習しました。以下のように、皆さんと共有して参考にしてください:

基本的な考え方: キーワード間の n - i 比較により、n - i + 1 個のレコードから最小のキーワードを持つレコードを選択し、その i と交換します。 -番目 (1

アルゴリズムの実装:

<?php
//简单选择排序
//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//简单选择排序算法
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    //记录第$i个元素后的所有元素最小值下标
    $min = $i;
    for($j = $i + 1;$j < $count;$j ++){
      if($arr[$j] < $arr[$min]){
        $min = $j;
      }
    }
    if($min != $i){
      swap($arr,$min,$i);
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);

実行結果:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

複雑さの分析: シンプルな選択ソート処理、必要な手数の記録回数を比較します。最良の場合、つまり、並べ替えられるレコードの初期状態はすでに正の順序になっており、レコードを移動する必要はありません。

最悪の場合、つまりソート対象のレコードの初期状態で最初のレコードが最も大きく、それ以降のレコードが昇順に並んでいる場合、移動する必要があるレコードの数は最大でも3件です(n-1)。単純選択ソート時に必要な比較回数は、初期状態でのソート対象のレコード列の配置とは関係ありません。 i=1 の場合は n-1 回の比較が必要となり、i=2 の場合は n-2 回の比較が必要となり、必要な比較の合計数は (n-1)+(n-2)+ …+2 となります。 +1=n(n-1)/2、つまり、比較演算の時間計算量は

、移動演算の時間計算量はO(n)です。 単純選択ソートは不安定なソートです。

この記事は「Dahua データ構造」から参照されています。将来の参考のためにここに記録されているだけです。批判しないでください。

関連する推奨事項:

以上がPHP ソート アルゴリズム シンプル セレクション ソート (シンプル セレクション ソート)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。