由于最近在找工作，面试中难免会遇到一些算法题，所以就用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;}