美文网首页数据结构和算法
常用排序算法的 PHP 实现

常用排序算法的 PHP 实现

作者: Stone_Zhuo | 来源:发表于2017-09-21 19:03 被阅读91次

排序概念

在计算机领域，排序是将原本无序的队列按照一定的规则分布而成为有序队列的过程，在程序开发中应用比较广泛。

排序种类

常见的排序算法有：冒泡排序，直接插入排序，折半插入排序，快速排序，计数排序，希尔排序，梳排序，选择排序。

排序实例

  • 冒泡排序
    冒泡排序是通过遍历队列并依次比较相邻的两个元素，把不符合顺序要求的元素进行交换，重复这一过程知道队列元素全部符合顺序要求为止。排序过程就好像水中的气泡往上冒一样，所以被成为冒泡排序。PHP实例如下：
// 由小到大排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
    for ($j = $i + 1;$j < $count;$j++) {
        if ($data[$i] > $data[$j]) {
            $tmp = $data[$i];
            $data[$i] = $data[$j];
            $data[$j] = $tmp;
        }
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
    for ($j = $i + 1;$j < $count;$j++) {
        if ($data[$i] < $data[$j]) {
            $tmp = $data[$i];
            $data[$i] = $data[$j];
            $data[$j] = $tmp;
        }
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 3
    [6] => 2
    [7] => 1
)
*/
  • 直接插入排序
    插入排序是依次将一个待排序元素插入已经排序的队列中的适当位置直到全部插入完成，直接插入排序是插入排序的一种。PHP实例如下：
// 由小到大直接插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
    if ($data[$i-1] > $data[$i]) {
        $tmp = $data[$i];
        $j = $i;
        while ($j > 0 && $data[$j - 1] > $tmp) {
            $data[$j] = $data[$j - 1];
            $j--;
        }
        $data[$j] = $tmp;
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小直接插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
    if ($data[$i-1] < $data[$i]) {
        $tmp = $data[$i];
        $j = $i;
        while ($j > 0 && $data[$j - 1] < $tmp) {
            $data[$j] = $data[$j - 1];
            $j--;
        }
        $data[$j] = $tmp;
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 2
    [6] => 3
    [7] => 1
)
*/
  • 折半插入排序
    折半插入排序是对直接插入排序的改进，将待排序元素与有序序列中间位置元素进行比较，根据比较结果确定待排元素继续比较的区间，直到找到合适的位置。PHP实例如下：
// 由小到大折半插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
    $left = 0;
    $right = $i - 1;
    $tmp = $data[$i];

    while ($left <= $right) {
        $middle = ($left + $right) / 2;
        if ($tmp < $data[$middle]) {
            $right = $middle - 1;
        } else {
            $left = $middle + 1;
        }
    }

    for ($j = $i;$j > $left;$j--) {
        $data[$j] = $data[$j - 1];
    }
    $data[$j] = $tmp;
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小折半插入排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 1;$i < $count;$i++) {
    $left = 0;
    $right = $i - 1;
    $tmp = $data[$i];

    while ($left <= $right) {
        $middle = ($left + $right) / 2;
        if ($tmp > $data[$middle]) {
            $right = $middle - 1;
        } else {
            $left = $middle + 1;
        }
    }

    for ($j = $i;$j > $left;$j--) {
        $data[$j] = $data[$j - 1];
    }
    $data[$j] = $tmp;
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 2
    [6] => 3
    [7] => 1
)
*/
  • 快速排序
    快速排序是对冒泡排序的改进，采用递归和分治的思想，将一个队列分成两个队列，其中一个队列中的元素都比第二个队列小，再对分割好的队列用同样的方式分割直到不能再分割为止，最后将分割出来的元素再按照分割后的顺序组合起来。PHP实例如下：
/*
 * 由小到大快速排序
 * @param array $param
 * @return array
 */
function quickSortAsc($param) {
    $count = count($param);
    if ($count <= 1) {
        return $param;
    }
    $base = $param[0];
    $small = [];
    $big = [];
    for ($i = 1;$i < $count;$i++) {
        if ($param[$i] > $base) {
            $big[] = $param[$i];
        } else {
            $small[] = $param[$i];
        }
    }
    return array_merge(quickSortAsc($small), [$base], quickSortAsc($big));
}
$data = [3, 5, 2, 34, 4, 7, 23, 1];
echo '<pre>';
print_r(quickSortAsc($data));
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

/*
 * 由大到小快速排序
 * @param array $param
 * @return array
 */
function quickSortAsc($param) {
    $count = count($param);
    if ($count <= 1) {
        return $param;
    }
    $base = $param[0];
    $small = [];
    $big = [];
    for ($i = 1;$i < $count;$i++) {
        if ($param[$i] > $base) {
            $big[] = $param[$i];
        } else {
            $small[] = $param[$i];
        }
    }
    return array_merge(quickSortAsc($big), [$base], quickSortAsc($small));
}
$data = [3, 5, 2, 34, 4, 7, 23, 1];
echo '<pre>';
print_r(quickSortAsc($data));
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 3
    [6] => 2
    [7] => 1
)
*/
  • 计数排序
    对于给定序列，直接将指定元素放在比它小的序列元素个数对应的序列位置上以完成排序的算法被成为计数排序。PHP实例如下：
// 由小到大计数排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$new_data = [];
for ($i = 0;$i < $count;$i++) {
    $location = 0;
    for ($j = 0;$j < $count;$j++) {
        if ($data[$i] > $data[$j]) {
            $location++;
        }
    }
    while (isset($new_data[$location]) && $location < $count) {
        $location++;
    }
    $new_data[$location] = $data[$i];
}
for ($i = 0;$i < $count;$i++) {
    $data[$i] = $new_data[$i];
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小计数排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$new_data = [];
for ($i = 0;$i < $count;$i++) {
    $location = 0;
    for ($j = 0;$j < $count;$j++) {
        if ($data[$i] < $data[$j]) {
            $location++;
        }
    }
    while (isset($new_data[$location]) && $location < $count) {
        $location++;
    }
    $new_data[$location] = $data[$i];
}
for ($i = 0;$i < $count;$i++) {
    $data[$i] = $new_data[$i];
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 2
    [6] => 3
    [7] => 1
)
*/
  • 希尔排序
    希尔排序是直接插入排序的改进版本，把队列下标按一定增量分组，对每组使用直接插入排序，随着增量减小每组的元素越来越多，当增量为1时整个队列是一组，算法结束。
// 由小到大希尔排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$random = 3;
$rank = 1;
while ($rank < $count / $random) {
    $rank = $random * $rank + 1;
}
while ($rank >= 1) {
    for ($i = $rank; $i < $count;$i++) {
        for ($j = $i;$j >= $rank;$j -= $rank) {
            if ($data[$j] < $data[$j - $rank]) {
                $tmp = $data[$j];
                $data[$j] = $data[$j - $rank];
                $data[$j - $rank] = $tmp;
            }
        }
    }
    $rank = intval($rank / $random);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小希尔排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$random = 3;
$rank = 1;
while ($rank < $count / $random) {
    $rank = $random * $rank + 1;
}
while ($rank >= 1) {
    for ($i = $rank; $i < $count;$i++) {
        for ($j = $i;$j >= $rank;$j -= $rank) {
            if ($data[$j] > $data[$j - $rank]) {
                $tmp = $data[$j];
                $data[$j] = $data[$j - $rank];
                $data[$j - $rank] = $tmp;
            }
        }
    }
    $rank = intval($rank / $random);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 3
    [6] => 2
    [7] => 1
)
*/
  • 梳排序
    梳排序是基于冒泡排序的，是对队列中固定距离处的元素进行比较和交换。PHP实例如下：
// 由小到大梳排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$step = intval($count / 1.4);
while ($step >= 1) {
    for ($i = 0; $i < $count;$i++) {
        if ($step + $i < $count && $data[$i] > $data[$step + $i]) {
            $tmp = $data[$i];
            $data[$i] = $data[$i + $step];
            $data[$i + $step] = $tmp;
        }
        if ($step + $i >= $count) {
            break;
        }
    }
    $step = intval($step / 1.4);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 3
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小梳排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
$step = intval($count / 1.4);
while ($step >= 1) {
    for ($i = 0; $i < $count;$i++) {
        if ($step + $i < $count && $data[$i] < $data[$step + $i]) {
            $tmp = $data[$i];
            $data[$i] = $data[$i + $step];
            $data[$i + $step] = $tmp;
        }
        if ($step + $i >= $count) {
            break;
        }
    }
    $step = intval($step / 1.4);
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 3
    [6] => 2
    [7] => 1
)
*/
  • 选择排序
    选择排序依次访问未排序队列部分并找出最小（或最大）的元素，将找到的元素放在未排序队列的最前面指导排序完成。PHP实例如下：
// 由小到大选择排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
    $index = $i;
    for ($j = $i + 1; $j < $count;$j++) {
        if ($data[$index] > $data[$j]) {
            $index = $j;
        }
    }
    if ($index != $i) {
        $tmp = $data[$index];
        $data[$index] = $data[$i];
        $data[$i] = $tmp;
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 23
    [7] => 34
)
*/

// 由大到小选择排序
$data = [3, 5, 2, 34, 4, 7, 23, 1];
$count = count($data);
for ($i = 0;$i < $count - 1;$i++) {
    $index = $i;
    for ($j = $i + 1; $j < $count;$j++) {
        if ($data[$index] < $data[$j]) {
            $index = $j;
        }
    }
    if ($index != $i) {
        $tmp = $data[$index];
        $data[$index] = $data[$i];
        $data[$i] = $tmp;
    }
}
echo '<pre>';
print_r($data);
echo '</pre>';
/*
Array
(
    [0] => 34
    [1] => 23
    [2] => 7
    [3] => 5
    [4] => 4
    [5] => 3
    [6] => 2
    [7] => 1
)
*/

本文首发于公众号：programmer_cc，转载请注明出处。


微信公众号.jpg

相关文章

  • 常用的排序算法

    常用的排序算法(PHP实现)_慕课手记

  • PHP常用数组排序算法

    title: PHP常用数组排序算法tags: [PHP,数组,排序,算法] 这几天写到的代码中，用到了许多对数组...

  • python 排序算法

    文章概述 介绍各大常用经典的排序算法和效率，以及python实现常用算法（冒泡排序，选择排序，快速排序，插入排序）...

  • 常用排序算法的 PHP 实现

    排序概念 在计算机领域，排序是将原本无序的队列按照一定的规则分布而成为有序队列的过程，在程序开发中应用比较广泛。 ...

  • 常用排序算法

    常用的排序算法 在此总结一下常用排序算法的代码实现 #include using namespace std;t...

  • Python一行代码实现快速排序

    上期文章排序算法——（2）Python实现十大常用排序算法为大家介绍了十大常用排序算法的前五种（冒泡、选择、插入、...

  • PHP - 快速排序

    使用PHP代码实现快速排序算法 快速排序是十分常用的高效率的算法，其思想是：先选一个标尺，用它把整个队列过一遍筛选...

  • 排序算法最强总结及其代码实现（Python/Java）

    前言 本文总结了常用的全部排序算法，内容包括： 排序算法的定义和思路 排序算法的代码实现：Python和Java，...

  • 常用数据结构及算法

    数据结构与算法——常用排序算法及其Java实现 - QueenKing - SegmentFault 思否

  • 排序算法的实现

    用java对常用内部排序算法的实现。 对冒泡排序，简单选择排序，直接插入排序，希尔排序，归并排序的简单实现（缺少快...

网友评论

    本文标题：常用排序算法的 PHP 实现

    本文链接：https://www.haomeiwen.com/subject/taaosxtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    数据结构和算法

    关于我们|服务条款|联系我们|常用排序算法的 PHP 实现|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！