PHP簡易選択ソートケースの詳細説明

今回は、PHP の単純な 選択ソート の詳細なケースの説明をお届けします。

基本的な考え方: キーワード間の n - i 個の比較を通じて、n - i + 1 個のレコードから最小のキーワードを持つレコードを選択し、それを i 番目のレコードと結合します (1 <= i < ; = n) 個のレコードを交換し、n-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^2)

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

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

PHP クイックソートアルゴリズムを使用する手順の詳細な説明

PHP 基数ソートを使用する手順の詳細な説明

以上がPHP簡易選択ソートケースの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。