PHPのデータ構造(4) 直接挿入ソート

直接挿入ソートは、ソート済みの配列にソート対象の要素をサイズ順に挿入することです。N 個の要素を持つ順序付けされていない配列を想定すると、ソートを完了するために N-1 回の挿入が実行されます。

たとえば、次のように、5 つの要素を持つ順序なし配列が挿入され、4 回ソートされます: $array(15,7,43,22,18)

初回::$ array( 15) ソート後、要素 7 を配列に挿入します: $array(7,15)

2 回目: $array(7,15) ソート後、要素 43 を配列に挿入します: $array(7 ,15) ,43)

3 回目: $array(7,15,43) ソート後、要素 22 を配列に挿入します: $array(7,15,22,43)

4 回目: $array(7,15,22,41) 要素 18 を配列に挿入し、並べ替えた後: $array(7,.15,18,22,43) 、並べ替えを完了します。

コードは次のように実装されます:

<pre name="code" class="php"><span style="font-size:18px;"><?php
	function insert_sort($array){

		$count=count($array);
		for($i=1;$i<$count;$i++){
			if($array[$i-1]>$array[$i]){
				$temp=$array[$i];
				$j=$i;
				while($j>0 && $array[$j-1]>$temp){
					$array[$j]=$array[$j-1];
					$j--;
				}
				$array[$j]=$temp;
			}

		}
		return $array;
	}


	$arr=array(4,1,17,9,88,37,43);
	$res=insert_sort($arr);
	foreach($res as $key => $values){
		echo "key:".($key+1)." value:".$values."<br/>";
	}
?>

以上、PHPのデータ構造(4)直接挿入ソートについて内容も含めて紹介しましたが、PHPチュートリアルに興味のある方の参考になれば幸いです。