code
function selectSort($arr) {
$len = count($arr);
for($i = 0 ; $i < $len - 1; $i ++) {
// 默認(rèn)第一個是最小值
$min = $i;
// 注意這里是從$i + 1 開始遍歷剩余的元素，選出最小值
for($n = $i + 1 ; $n < $len; $n ++) {
if($arr[$n] < $arr[$min]) {
$min = $n;
}
}
// 如果最小值不是當(dāng)前默認(rèn)的最小值，那么進(jìn)行替換
if($min != $i) {
$t = $arr[$i];
$arr[$i] = $arr[$min];
$arr[$min] = $t;
}
}
return $arr;
}
冒泡排序
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，除了最后一個。持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
簡單解釋
要比較N輪，每輪都要比較N-當(dāng)前輪次的次數(shù)， 每次都會選出一個最大值放到后面（有點(diǎn)抽象）
代碼
function bubbleSort($arr) {
$len = count($arr);
// 這里比較N次
for($i = 0; $i< $len - 1; $i++) {
// 每次比較實際上都要-$i，因為每次比較結(jié)束后最后一個值就不用參與下次比較了
for($n = 0; $n < $len - 1 - $i; $n ++) {
if($arr[$n] > $arr[$n + 1]) {
$t = $arr[$n];
$arr[$n] = $arr[$n + 1];
$arr[$n + 1] = $t;
}
}
}
return $arr;
}
快速排序（真的很快）
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
簡單解釋
這個真的更抽象，因為，就是將小的放一邊，大的放一邊，然后遞歸出來
code
function quickSort($arr) {
$len = count($arr);
// 因為是遞歸，所以如果最后的數(shù)組可能是空的也可能是1個，那么就沒有可比較的了，直接返回
if($len <= 1) {
return $arr;
}
$base = $min = $max = [];
$base_item = $arr[0];
for($i = 0; $i < $len ; $i++) {
if($arr[$i] < $base_item) {
$min[] = $arr[$i];
}elseif($arr[$i] > $base_item) {
$max[] = $arr[$i];
}else {
$base[] = $arr[$i];
}
}
$min = quickSort($min);
$max = quickSort($max);
// 每次構(gòu)造新的序列
return array_merge($min,$base,$max);
}
性能測試
這三個排序算法的時間復(fù)雜度是不一樣的，我們來測試下性能。我們用下面代碼來生成散列數(shù)組。
$arr = range(0,$argv[1]);
shuffle($arr);
然后執(zhí)行上面三個方法
$time = execTime();
// 快速排序
quickSort($arr);
$time = execTime($time);
// 選擇排序
selectSort($arr);
$time = execTime($time);
// 冒泡排序
bubbleSort($arr);
$time = execTime($time);
// 這個是計算毫秒耗時的方法
function execTime($microTime = 0) {
$microTime && var_dump(microtime(true)*1000 - $microTime);
return microtime(true)*1000;
}
看下執(zhí)行結(jié)果，果然最快的是快速排序
php sort_practice.php 10
float(0.0419921875)
float(0.011962890625)
float(0.011962890625)
php sort_practice.php 100
float(0.30908203125)
float(0.396240234375)
float(0.779052734375)
php sort_practice.php 200
float(0.687744140625)
float(1.93994140625)
float(3.37890625)
php sort_practice.php 300
float(0.85400390625)
float(3.222900390625)
float(8.123046875)
php sort_practice.php 400
float(1.23193359375)
float(5.857177734375)
float(11.824951171875)
php sort_practice.php 500
float(1.559814453125)
float(8.73291015625)
float(21.15087890625)
php sort_practice.php 600
float(1.70703125)
float(14.300048828125)
float(30.343994140625)
php sort_practice.php 700
float(2.265869140625)
float(18.0390625)
float(41.654052734375)
php sort_practice.php 800
float(2.581298828125)
float(24.72998046875)
float(53.56005859375)
php sort_practice.php 900
float(2.682861328125)
float(31.9560546875)
float(65.988037109375)
php sort_practice.php 1000
float(3.18701171875)
float(36.010986328125)
float(78.216064453125)
php sort_practice.php 2000
float(6.450927734375)
float(151.62475585938)
float(313.64624023438)
php sort_practice.php 3000
float(11.026123046875)
float(362.6640625)
float(721.11572265625)
php sort_practice.php 4000
float(15.346923828125)
float(667.11791992188)
float(1314.2221679688)
php sort_practice.php 5000
float(20.559814453125)
float(1029.8937988281)
float(2057.3466796875)
php sort_practice.php 6000
float(27.767822265625)
float(1534.2431640625)
float(2917.7407226562)
php sort_practice.php 7000
float(33.481201171875)
float(2083.5861816406)
float(3984.7060546875)
php sort_practice.php 8000
float(38.852783203125)
float(2606.0270996094)
float(5157.6708984375)
php sort_practice.php 9000
float(42.02587890625)
float(3436.4509277344)
float(6638.451171875)
php sort_practice.php 10000
float(45.932861328125)
float(4640.3000488281)
float(8474.2751464844)
二分搜索查找
再寫一個經(jīng)典搜索
先從中間開始找，遞歸類似快速排序
$arr = range(0, $argv[1]);
$value = mt_rand(0, count($arr));
var_dump($value);
function binSearch($value, $arr) {
if(!$arr) {
return false;
}
$sign = floor(count($arr)/2);
$middle = $arr[$sign];
if($middle == $value) {
var_dump($middle);
}else {
binSearch($value,array_slice($arr, 0, $sign));
binSearch($value,array_slice($arr, $sign + 1));
}
}
binSearch($value,$arr);
