スタックソート(php実装)

ヒープ・ソートの基本手順:
1:無秩序シーケンスを1つのスタックに構成する.
2:スタックトップ要素と最後の要素を交換し、交換後、スタック構造が破壊されたため、スタックをリセットします.
初期化スタックと交換後のリセットスタックの違いは、スタックを初期化するときに最後の非リーフノードからノード位置を調整し、スタック上部要素を交換した後のリセットはスタック上部要素の位置を調整するだけである.

<?php 

/**

 *    

 */





function heapSort($arr){

	$len = count($arr);

	initHeap($arr);//    

	for($end=$len-1;$end>0;$end--){//            

		$tmp = $arr[$end];

		$arr[$end] = $arr[0];

		$arr[0] = $tmp;

		

		//   ，          

		adjustHeap($arr,0,$end-1);//$end-1

	}

	return $arr;

}



function initHeap(&$arr){

	$len = count($arr);

	//           ，    

	for($start=floor($len/2)-1;$start>=0;$start--){

		adjustHeap($arr,$start,$len-1);

	}

}



/*

 * $arr      

 * $start         （          ，-1）

 * $end     

 */

function adjustHeap(&$arr,$start,$end){

	$max = $start;

	$lchild_index = 2*($start+1)-1;

	$rchild_index = 2*($start+1);

	

	if($lchild_index<=$end){

		if($arr[$lchild_index]>$arr[$max]){

			$max = $lchild_index;

		}

		

		if($rchild_index<=$end&&$arr[$rchild_index]>$arr[$max]){

			$max = $rchild_index;

		}

		

		

	}

	

	if($max !=$start){

		$tmp = $arr[$start];

		$arr[$start] = $arr[$max];

		$arr[$max] = $tmp;

		

		adjustHeap($arr, $max, $end);

 	}

}



$arr = array(2,4,5,2,4,6,3,1,2,7,8);

echo count($arr);

print_r(heapSort($arr));

?>