一些排序算法的php实现

/ 0 评 / 阅读 474

在 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 &lt; $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] &gt; $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 &lt;= 1) {
        return $array;
    } else {
        $pivot = $array[0];
        $less = $greater = [];
        for ($i = 1; $i &lt; $length; $i++) {
            if ($array[$i] &lt; $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 &lt; $count - 1; $i++) {
        $min = $array[$i];
        $key = $i;
        for ($j = $i + 1; $j &lt; $count; $j++) {
            if ($array[$j] &lt; $min) {
                $min = $array[$j];
                $key = $j;
            }
        }
        if ($key &gt; $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 &lt; $length; $i++) {
        $j = $i;
        do {
            $continue = false;
            if ($array[$i] &lt; $sort[$j - 1]) {
                $j--;
                $continue = true;
            }
        } while ($continue);
        if ($j &lt; $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 &gt; 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 &lt; $length - 1; $i++) {
        if (count($array1) == 0 || count($array2) == 0) {
            break;
        }
        if ($array1[0] &lt;= $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 &lt;= 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 &lt; $length; $i++) {
            if ($array[$i] &lt; $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 &lt; 1000; $i++) {
        $count_arr[$i] = 0;
    }
    for ($i = 0; $i &lt; $length; $i++) {
        $count_arr[$array[$i]]++;
    }
    $result = [];
    for ($i = 0; $i &lt; 1000; $i++) {
        for ($j = 0; $j &lt; $count_arr[$i]; $j++) {
            $result[] = $i;
        }
    }
    return $result;
}

/**
 * 基数排序
 * @param $array
 * @return array
 */
function radix($array)
{
    $length = count($array);
    $new_array = [];

    for ($i = 0; $i &lt; $length; $i++) {
        $_num = $array[$i];
        $num = [];
        for ($j = 0; $j &lt; 3; $j++) {
            $int = $_num % 10;
            array_unshift($num, $int);
            $_num = $_num / 10;
        }
        $new_array[] = $num;
    }
    for ($i = 0; $i &lt; 3; $i++) {
        $bucket = [];
        for ($j = 0; $j &lt; 10; $j++) {
            $bucket[$j] = [];
        }
        for ($j = 0; $j &lt; $length; $j++) {
            $bucket[$new_array[$j][2 - $i]][] = $new_array[$j];
        }
        $new_array = [];
        for ($j = 0; $j &lt; 10; $j++) {
            for ($k = 0; $k &lt; count($bucket[$j]); $k++) {
                $new_array[] = $bucket[$j][$k];
            }
        }
    }
    for ($i = 0; $i &lt; $length; $i++) {
        $temp = $new_array[$i];
        $new_array[$i] = 0;
        for ($j = 0; $j &lt; 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,'基数');

参考网站:

https://visualgo.net/en

发表评论

电子邮件地址不会被公开。 必填项已用*标注