PHP 的 qsort

將參考連接中的 qsort 轉了用 PHP 來寫.

<?php
function exchange(&$a, $i, $j) {
	if ($i == $j) {
		return;
	}
	
	$a[$i] ^= $a[$j];
	$a[$j] ^= $a[$i];
	$a[$i] ^= $a[$j];
}

// one finger
function partition(&$a, $p, $r) {
	$x = $a[$r];
	$i = $p - 1;
	for($j = $p; $j < $r; ++$j) {
		if ($a[$j] < $x) {
			++$i;
			exchange($a, $i, $j);
		}
	}
	exchange($a, $i + 1, $r);
	return $i + 1;
}

// two finger
/*
function partition(&$a, $p, $r) {
	$x = $a[$r];
	
	$left = $p;
	$right = $r - 1;
	while($left <= $right) {
		if ($a[$left] < $x) {
			$left++;
		}
		
		if ($left <= $right && $a[$right] >= $x) {
			$right--;
		}
		
		if ($left < $right && $a[$left] >= $x && $a[$right] <= $x) {
			exchange($a, $left, $right);
		}
	}
	
	exchange($a, $left, $r);
	
	return $left;
}
*/

function quicksort(&$a, $p, $r) {
	if ($p >= $r) {
		return;
	}
	
	$q = partition($a, $p, $r);
	quicksort($a, $p, $q - 1);
	quicksort($a, $q + 1, $r);
}

function main() {
	$a = array(2, 8, 7, 1, 3, 5, 6, 4, 80, 100, -100, -10);
	
	quicksort($a, 0, sizeof($a) - 1);
	
	for($i=0;$i<sizeof($a);$i++) {
		printf("%d ", $a[$i]);
	}
	printf("\n");
}

main();
?>

參考: http://blog.csdn.net/moonvs2010/article/details/8607044