PHP 単純な選択ソート アルゴリズム学習共有

この記事では主に PHP の単純な選択ソートのアルゴリズムを詳しく紹介します。興味のある方はぜひ参考にしてください。

この記事の例は、参考のために PHP での単純な選択ソートの具体的なコードを共有します。具体的な内容は次のとおりです

基本的な考え方:

キーワード間の 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);

複雑さの分析:

単純な選択ソートプロセスでは、移動する必要があるレコードの数は比較的少ないです。最良の場合、つまり、並べ替えられるレコードの初期状態はすでに正の順序になっており、レコードを移動する必要はありません。

最悪の場合、つまり、ソート対象のレコードの初期状態では、最初のレコードが最も大きく、後続のレコードは小さいレコードから大きいレコードの順に配置され、移動する必要があるレコードの数が増加します。は最大 3 (n-1) です。単純選択ソート時に必要な比較回数は、初期状態でのソート対象のレコード列の配置とは関係ありません。 i=1 の場合は n-1 回の比較が必要で、i=2 の場合は n-2 回の比較が必要です。など、必要な比較の合計数は (n-1)+(n-2)+ ... になります。 +2+1=n(n-1)/2、つまり、比較演算の時間計算量は O(n^2)、移動演算の時間計算量は O(n) です。

単純選択ソートは不安定なソートです。

関連する推奨事項:

PHPソートアルゴリズムシリーズの直接選択ソートの詳細説明

PHPソートアルゴリズムシリーズのバケットソートの詳細説明_phpスキル

PHPでヒルソートアルゴリズムを実装する方法の詳細分析

以上がPHP 単純な選択ソート アルゴリズム学習共有の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。