唯倚社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 313|回复: 2

技术干货丨php常见的五种排序算法

[复制链接]

1

主题

2

帖子

16

积分

LV1

Rank: 1

积分
16
发表于 2017-10-27 00:52:38 | 显示全部楼层 |阅读模式

轻松玩转社区

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

[color=rgb(62, 62, 62) ]算法是很多phper容易忽略和薄弱的环节,本文用php实现常见的五种排序算法,希望能够加深各位小伙伴对排序算法的理解。

1.插入排序

[color=rgb(62, 62, 62) ]以数组第二个数字为基准 假定该数组之前的数字都是排好序的,相互比较大小,比该数字小的放该基准数字的前面,依次往后移动,直到数组尾部,整个数组排序完毕.插入排序是稳定算法。
   function charu($arr) {    $count = count($arr);    for ($i = 1; $i < $count; $i++) {        #以数组第一个数字为基准        $temp = $arr[$i];        #控制循环并进行交换        for ($j = $i - 1; $j >= 0; $j--) {            if ($temp < $arr[$j]) {                $arr[$j + 1] = $arr[$j];                $arr[$j] = $temp;            } else {                break;            }        }    }    return $arr;}
2.选择排序

[color=rgb(62, 62, 62) ]默认以第一个数字为基准数字,每次以基准数字从待排数字中找出最小(大)的数字,顺序放在已经排好数据列的最后,选择排序是不稳定的。
function xuanze($arr) { $count = count($arr);    for ($i = 0; $i < $count - 1; $i++) {        $min = $i;        for ($j = $i + 1; $j < $count; $j++) {            if ($arr[$min] > $arr[$j]) {                $min = $j;        }        }        if ($i != $min) {            $temp = 0;            $temp = $arr[$min];            $arr[$min] = $arr[$i];            $arr[$i] = $temp;        }    }    return $arr;}
3.冒泡排序

[color=rgb(62, 62, 62) ]相邻的两个数字进行比较 找出最小的放在前面 大数放后面 依次比较。冒泡算法是稳定算法。
function maopao($arr) {    $count = count($arr);    for ($i = 0; $i < $count - 1; $i++) {        for ($j = $i + 1; $j < $count; $j++) {            if ($arr[$i] > $arr[$j]) {                $temp = 0;                $temp = $arr[$j];                $arr[$j] = $arr[$i];                $arr[$i] = $temp;            }        }    }    return $arr;}
4.快速排序

[color=rgb(62, 62, 62) ]以数组的第一个数字为基准点 以这个基准数字为参考点 比该数字大的放右边 比该数字小的放左边 然后在根据切分出来的数组进行递归 到只剩一元素时停止递归.快速排序是不稳定算法。
function kuaisu($arr) {    $count = count($arr);    if ($count <= 1) {        return $arr;    }    $temp = $arr[0];    $left = $right = [];    for ($i = 1; $i < $count; $i++) {        if ($temp > $arr[$i]) {            $left[] = $arr[$i];        } else {            $right[] = $arr[$i];        }    }    $left = kuaisu($left);    $right = kuaisu($right);    return array_merge($left, array($temp), $right);}
5.木桶排序

[color=rgb(62, 62, 62) ]首先产生两个数字,最大值和最小值,然后根据两个数字的值决定要创建多少个桶装数据,每个 桶装数据按key编好号码,按数组内的数字指定桶的出现次数。然后输出所有指定桶。木桶算法是不稳定算法。
function mutong($arr) {    $min = min($arr);    $max = max($arr);    $count = count($arr);    $buffer = array_fill($min, $max - $min + 1, 0);    for ($i = 0; $i < $count - 1; $i++) {        $buffer[$arr[$i]] ++;    }    //根据统计桶内的次数输出桶内的数字    for ($i = $min; $i < $max + 1; $i++) {        for ($j = 0; $j < $buffer[$i]; $j++) {            $result[] = $i;        }    }    return $result;}
[color=rgb(62, 62, 62) ]tips:关于稳定排序和不稳定排序:

[color=rgb(62, 62, 62) ]比如在一个数组中,有[1,3,5,10,5],第一个5我们称作r5,第二个5我们称作j5.在经过排序后,r5还是在j5之前的,我们称作稳定算法,反之称作不稳定算法。
[color=rgb(62, 62, 62) ]最后贴出算法时间复杂度和空间复杂图的图片:

文章素材来源于网络,版权归作者所有,侵删。



               
                    

来源地址:http://mp.weixin.qq.com/s?src=3×tamp=1498154924&ver=1&signature=kS3riMqOqbFktIP44Uy*EVemyvyH6v*bLV1YgzyBjPPYiDa8ZPsSFBiM92sifHsfVGkXKg87fVVw3fY4IsLCVJyr0nsfuDynKUfWRLi8uxx0MDsAHHFW-mS9FWaZ-3PwqlWkShQ2bdKgrEaiaAAvfsRNVkTR2t61DfUtZkVo1Pw=

137

主题

307

帖子

3811

积分

LV3

Rank: 3Rank: 3

积分
3811

最佳新人

发表于 2017-10-28 11:05:38 | 显示全部楼层
66666666
回复

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|weiecn ( 湘ICP备14002058号 )

GMT+8, 2018-11-21 00:20 , Processed in 0.064228 second(s), 14 queries , Redis On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表