Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
八大排序算法的 PHP 实现 和 效率测试
<?php
$num = 1000;
$times = 3;
$algorithms = array('insert', 'shell', 'bubble', 'quick', 'select', 'heap', 'merge', 'radix');
$arr = array();
while (count($arr) < $num) {
$key = rand(1, $num * 10);
$arr[$key] = 1;
}
$arr = array_keys($arr);
$arrOk = array();
//$arr = [6, 15, 41, 49, 69, 40, 45, 91, 46, 13];
//echo 'Origin: ' . "\t" . implode(', ', $arr) . PHP_EOL;
foreach ($algorithms as $algorithm) {
echo $algorithm . PHP_EOL;
$func = $algorithm . '_sort';
for ($i = 1; $i <= $times; $i++) {
echo $i . "\t";
$startTime = microtime(true);
$_tmpArr = $arr;
$arr2 = $func($_tmpArr);
if (empty($arrOk)) {
$arrOk = $arr2;
}
if ($arrOk != $arr2) {
echo 'Error: ' . PHP_EOL;
echo 'Origin: ' . "\t" . implode(', ', $arr) . PHP_EOL;
echo 'Right:' . "\t" . implode(', ', $arrOk) . PHP_EOL;
echo 'Error:' . "\t" . implode(', ', $arr2) . PHP_EOL;
}
$endTime = microtime(true);
echo ($endTime - $startTime) . PHP_EOL;
}
//sleep(1);
}
echo PHP_EOL;
//echo implode(', ', $arrOk) . PHP_EOL;
/** ========================================= */
/**
* 插入排序
*
* @param array $lists
* @return array
*/
function insert_sort(array $lists)
{
for ($i = 1; $i < count($lists); $i++) {
$key = $lists[$i];
for ($j = $i - 1; $j >= 0 && $lists[$j] > $key; $j--) {
$lists[$j + 1] = $lists[$j];
$lists[$j] = $key;
}
}
return $lists;
}
/**
* 希尔排序 标准
*
* @param array $lists
* @return array
*/
function shell_sort(array $lists)
{
$n = count($lists);
$step = 2;
$gap = intval($n / $step);
while ($gap > 0) {
for ($gi = 0; $gi < $gap; $gi++) {
for ($i = $gi; $i < $n; $i += $gap) {
$key = $lists[$i];
for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
$lists[$j + $gap] = $lists[$j];
$lists[$j] = $key;
}
}
}
$gap = intval($gap / $step);
}
return $lists;
}
/**
* 冒泡排序
*
* @param array $lists
* @return array
*/
function bubble_sort(array $lists)
{
$num = count($lists);
for ($i = 0; $i < $num; $i++) {
for ($j = $i + 1; $j < $num; $j++) {
if ($lists[$i] > $lists[$j]) {
$key = $lists[$i];
$lists[$i] = $lists[$j];
$lists[$j] = $key;
}
}
}
return $lists;
}
/**
* 快速排序
*
* @param array $lists
* @param $left
* @param $right
* @return array
*/
function quick_sort(array &$lists, $left = 0, $right = null)
{
if (is_null($right)) {
$right = count($lists) - 1;
}
if ($left >= $right) {
return $lists;
}
$key = $lists[$left];
$low = $left;
$high = $right;
while ($left < $right) {
while ($left < $right && $lists[$right] > $key) {
$right--;
}
$lists[$left] = $lists[$right];
while ($left < $right && $lists[$left] < $key) {
$left++;
}
$lists[$right] = $lists[$left];
}
$lists[$right] = $key;
quick_sort($lists, $low, $left - 1);
quick_sort($lists, $left + 1, $high);
return $lists;
}
/**
* 直接选择排序
*
* @param array $lists
* @return array
*/
function select_sort(array $lists)
{
$n = count($lists);
for ($i = 0; $i < $n; $i++) {
$key = $i;
for ($j = $i + 1; $j < $n; $j++) {
if ($lists[$j] < $lists[$key]) {
$key = $j;
}
}
$val = $lists[$key];
$lists[$key] = $lists[$i];
$lists[$i] = $val;
}
return $lists;
}
/**
* 堆排序
*
* @param array $lists
* @return array
*/
function heap_sort(array $lists)
{
$n = count($lists);
build_heap($lists);
while (--$n) {
$val = $lists[0];
$lists[0] = $lists[$n];
$lists[$n] = $val;
heap_adjust($lists, 0, $n);
//echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
}
return $lists;
}
function build_heap(array &$lists)
{
$n = count($lists) - 1;
for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
heap_adjust($lists, $i, $n + 1);
//echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
}
//echo "build ok: " . implode(', ', $lists) . PHP_EOL;
}
function heap_adjust(array &$lists, $i, $num)
{
if ($i > $num / 2) {
return;
}
$key = $i;
$leftChild = $i * 2 + 1;
$rightChild = $i * 2 + 2;
if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
$key = $leftChild;
}
if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
$key = $rightChild;
}
if ($key != $i) {
$val = $lists[$i];
$lists[$i] = $lists[$key];
$lists[$key] = $val;
heap_adjust($lists, $key, $num);
}
}
/**
* 归并排序
*
* @param array $lists
* @return array
*/
function merge_sort(array $lists)
{
$n = count($lists);
if ($n <= 1) {
return $lists;
}
$left = merge_sort(array_slice($lists, 0, floor($n / 2)));
$right = merge_sort(array_slice($lists, floor($n / 2)));
$lists = merge($left, $right);
return $lists;
}
function merge(array $left, array $right)
{
$lists = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$lists[] = $left[$i];
$i++;
} else {
$lists[] = $right[$j];
$j++;
}
}
$lists = array_merge($lists, array_slice($left, $i));
$lists = array_merge($lists, array_slice($right, $j));
return $lists;
}
/**
* 基数排序
*
* @param array $lists
* @return array
*/
function radix_sort(array $lists)
{
$radix = 10;
$max = max($lists);
$k = ceil(log($max, $radix));
if ($max == pow($radix, $k)) {
$k++;
}
for ($i = 1; $i <= $k; $i++) {
$newLists = array_fill(0, $radix, []);
for ($j = 0; $j < count($lists); $j++) {
$key = $lists[$j] / pow($radix, $i - 1) % $radix;
$newLists[$key][] = $lists[$j];
}
$lists = [];
for ($j = 0; $j < $radix; $j++) {
$lists = array_merge($lists, $newLists[$j]);
}
}
return $lists;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.