由于最近在找工作，面试中难免会遇到一些算法题，所以就用PHP把七大排序算法都实现了一遍，也当做是一种复习于沉淀。
- 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序 5. 希尔排序 6. 归并排序 7. 堆排序(较麻烦)
/**
* 冒泡排序
*/
function bubble($arr) {
$length = count($arr);
for ($i=1; $i<$length; ++$i) {
for ($j=0; $j < $length-$i; ++$j) {
if ($arr[$j] > $arr[$j+1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
return $arr;
}
/**
* 选择排序
*/
function select($arr) {
$length = count($arr);
for ($i=0; $i<$length-1; ++$i) {
$minIndex = $i;
for ($j=$i+1; $j<$length; ++$j) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
if ($minIndex != $i) {
$tmp = $arr[$minIndex];
$arr[$minIndex] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
/**
* 插入排序
*/
function insert($arr) {
$length = count($arr);
for ($i=1; $i<$length; ++$i) {
$tmp = $arr[$i];
for ($j=$i-1; $j>=0; --$j) {
if ($tmp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
} else {
break;
}
}
}
return $arr;
}
/**
* 快速排序
*/
function fast($arr) {
$length = count($arr);
if ($length < 1) {
return [];
}
$mid = $arr[0];
$left = [];
$right = [];
for ($i=1; $i<$length; ++$i) {
if ($arr[$i] < $mid) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
$sortLeft = fast($left);
$sortRight = fast($right);
return array_merge($sortLeft, [$mid], $sortRight);
}
/**
* 归并排序
*/
function merge($arr) {
$length = count($arr);
if ($length < 2) {
return $arr;
}
$left = [];
$right = [];
for ($i=0; $i<$length; ++$i) {
if ($i < $length/2) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
$left = merge($left);
$right = merge($right);
$merge = [];
while (count($left) > 0 && count($right) >0) {
if ($left[0] < $right[0]) {
$merge[] = array_shift($left);
} else {
$merge[] = array_shift($right);
}
}
if (count($left) > 0) {
$merge = array_merge($merge, $left);
} elseif (count($right) > 0) {
$merge = array_merge($merge, $right);
}
return $merge;
}
/**
* 希尔排序
*/
function shell($arr) {
$length = count($arr);
for ($gap = floor($length/2); $gap >0; $gap = floor($gap/2)) {
for ($i=$gap; $i<$length; $i += $gap) {
$tmp = $arr[$i];
for ($j=$i-$gap; $j>=0; $j -= $gap) {
if ($tmp < $arr[$j]) {
$arr[$j+$gap] = $arr[$j];
$arr[$j] = $tmp;
} else {
break;
}
}
}
echo $gap."\n";
}
return $arr;
}
/**
* 堆排序
*/
function heap($arr) {
$length = count($arr);
for ($i=floor($length/2)-1; $i>=0; --$i) {
$arr = adjustHeap($arr, $i, $length);
}
for ($i=$length-1; $i>=0; --$i) {
$tmp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $tmp;
$arr = adjustHeap($arr, 0, $i);
}
return $arr;
}
function adjustHeap($arr, $index, $length) {
$lchild = 2*$index+1;
$rchild = 2*$index+2;
$max = $index;
if ($index<=floor($length/2)-1) {
if ($lchild<$length && $arr[$lchild] > $arr[$max]) {
$max = $lchild;
}
if ($rchild<$length && $arr[$rchild] > $arr[$max]) {
$max = $rchild;
}
if ($max != $index) {
$tmp = $arr[$index];
$arr[$index] = $arr[$max];
$arr[$max] = $tmp;
$arr = adjustHeap($arr, $max, $length);
}
}
return $arr;
}