在 VisuAlgo 上看到一些排序算法的原理，于是就想着用php来做一遍。做完之后还是很有收获的。这里贴一下代码。没有仔细打磨，应该多多少少可以写的更好的。
这里顺便说一下这些排序算法的思路吧，不过都是个人理解，仅当参考。
冒泡排序：大概是我们最熟悉的了，就是不断一遍一遍比较相邻元素的大小，直到没有元素再交换为止。因此最坏的情况下，需要对比交换 n² 次。
快速排序：这个算法在自己的测试里是最快的。其思路就是选择第一个元素作为一个“轴”，遍历剩余数组，把比它大的放右边，比它小的放左边，再对左右两边递归重复操作。
随机快速排序：其实就是一个快速排序的优化版，它不选择第一个元素作为“轴”，而是随机选择，这能防止对一些已经接近排序好的数组出现效率低下的情况，需要 n² 次交换。在自己的测试里，相较于通常的快速排序，随机快排貌似稳定一些（耗时波动小）。
选择排序：说白了就是不断把最小的元素移到前面。不断遍历剩余的数组，找到次小的元素。
插入排序：如果看着 VisuAlgo，其实还是挺直观的。就是遍历元素，当前元素不断和之前的元素比较，直到之前的元素比自己小，并移动当前元素到这个元素之后。
归并排序：刚开始让人挺难理解的一种算法。现在想来，就是不断递归的和相邻数组的第一个元素比较。例如，1到8的数组，分成1到8个子数组，[1]和[2]比较，[3]和[4]比较，等等。完了之后合并为[1,2]和[3,4]，然后[1,2]和[3,4]的元素比较，再合并，直到顶层 。
计数排序：感觉只适用于已知一定范围的随机数组的算法。例如，已知一个随机数组的元素的范围在1到100之间，那么直接统计1到100的数出现的次数，然后根据统计结果重新组合数组。
基数排序：感觉同上。将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
<?php
set_time_limit(0);
ini_set('display_errors', 'On');
error_reporting(7);
/**
* 创建随机数组
* @param int $length
* @return array
*/
function create($length = 100)
{
$array = [];
for ($i = 0; $i < $length; $i++) {
$array[] = mt_rand(0, 999);
}
return $array;
}
/**
* 冒泡排序
* @param $array
* @return mixed
*/
function bubble($array)
{
do {
$has = 0;
for ($i = 0; $i 1; $i++) {
if ($array[$i] > $array[$i + 1]) {
$temp = $array[$i];
$array[$i] = $array[$i + 1];
$array[$i + 1] = $temp;
$has++;
}
}
} while ($has);
return $array;
}
/**
* 快速排序
* @param $array
* @return array
*/
function quick($array)
{
$length = count($array);
if ($length <= 1) {
return $array;
} else {
$pivot = $array[0];
$less = $greater = [];
for ($i = 1; $i < $length; $i++) {
if ($array[$i] < $pivot) {
$less[] = $array[$i];
} else {
$greater[] = $array[$i];
}
}
return array_merge(quick($less), [$pivot], quick($greater));
}
}
/**
* 选择排序
* @param $array
* @return mixed
*/
function selection($array)
{
$count = count($array);
for ($i = 0; $i < $count - 1; $i++) {
$min = $array[$i];
$key = $i;
for ($j = $i + 1; $j < $count; $j++) {
if ($array[$j] < $min) {
$min = $array[$j];
$key = $j;
}
}
if ($key > $i) {
$temp = $array[$i];
$array[$i] = $min;
$array[$key] = $temp;
}
}
return $array;
}
/**
* 插入排序
* @param $array
* @return array
*/
function insertion($array)
{
$length = count($array);
$sort[] = $array[0];
for ($i = 1; $i < $length; $i++) {
$j = $i;
do {
$continue = false;
if ($array[$i] < $sort[$j - 1]) {
$j--;
$continue = true;
}
} while ($continue);
if ($j < $i) {
$sort = array_merge(array_slice($sort, 0, $j), [$array[$i]], array_slice($sort, $j));
} else {
$sort[] = $array[$i];
}
}
return $sort;
}
/**
* 归并排序
* @param $array
* @return array
*/
function merge($array)
{
$length = count($array);
$half = (int)ceil($length / 2);
$result = [];
if ($length > 2) {
$array1 = array_slice($array, 0, $half);
$array2 = array_slice($array, $half);
$array = array_merge($result, merge($array1), merge($array2));
}
$array1 = array_slice($array, 0, $half);
$array2 = array_slice($array, $half);
for ($i = 0; $i < $length - 1; $i++) {
if (count($array1) == 0 || count($array2) == 0) {
break;
}
if ($array1[0] <= $array2[0]) {
$result[] = array_shift($array1);
} else {
$result[] = array_shift($array2);
}
}
return array_merge($result, $array1, $array2);
}
/**
* 随机快速排序
* @param $array
* @return array
*/
function randomQuick($array)
{
$length = count($array);
if ($length <= 1) {
return $array;
} else {
$key = mt_rand(0, ($length - 1));
$temp = $array[0];
$array[0] = $array[$key];
$array[$key] = $temp;
$pivot = $array[0];
$less = $greater = [];
for ($i = 1; $i < $length; $i++) {
if ($array[$i] < $pivot) {
$less[] = $array[$i];
} else {
$greater[] = $array[$i];
}
}
return array_merge(quick($less), [$pivot], quick($greater));
}
}
/**
* 基数排序
* @param $array
* @return array
*/
function counting($array)
{
$length = count($array);
$count_arr = [];
for ($i = 0; $i < 1000; $i++) {
$count_arr[$i] = 0;
}
for ($i = 0; $i < $length; $i++) {
$count_arr[$array[$i]]++;
}
$result = [];
for ($i = 0; $i < 1000; $i++) {
for ($j = 0; $j < $count_arr[$i]; $j++) {
$result[] = $i;
}
}
return $result;
}
/**
* 基数排序
* @param $array
* @return array
*/
function radix($array)
{
$length = count($array);
$new_array = [];
for ($i = 0; $i < $length; $i++) {
$_num = $array[$i];
$num = [];
for ($j = 0; $j < 3; $j++) {
$int = $_num % 10;
array_unshift($num, $int);
$_num = $_num / 10;
}
$new_array[] = $num;
}
for ($i = 0; $i < 3; $i++) {
$bucket = [];
for ($j = 0; $j < 10; $j++) {
$bucket[$j] = [];
}
for ($j = 0; $j < $length; $j++) {
$bucket[$new_array[$j][2 - $i]][] = $new_array[$j];
}
$new_array = [];
for ($j = 0; $j < 10; $j++) {
for ($k = 0; $k < count($bucket[$j]); $k++) {
$new_array[] = $bucket[$j][$k];
}
}
}
for ($i = 0; $i < $length; $i++) {
$temp = $new_array[$i];
$new_array[$i] = 0;
for ($j = 0; $j < 3; $j++) {
$new_array[$i] += $temp[2 - $j] * pow(10, $j);
}
}
return $new_array;
}
function print_result($callable, $array, $name)
{
$begin = microtime(true);
$result = $callable($array);
$end = microtime(true);
echo $name . '排序，用时：' . (($end - $begin) * 1000) . 'ms' . PHP_EOL;
echo '排序结果：' . implode(',', $result) . PHP_EOL . PHP_EOL;
}
echo PHP_EOL;
$array = create();
echo '原始数组：' . implode(',', $array) . PHP_EOL . PHP_EOL;
print_result('bubble',$array,'冒泡');
print_result('quick',$array,'快速');
print_result('selection',$array,'选择');
print_result('insertion',$array,'插入');
print_result('merge',$array,'归并');
print_result('randomQuick',$array,'随机快速');
print_result('counting',$array,'计数');
print_result('radix',$array,'基数');参考网站：