# 【一】.冒泡排序
思路分析：
> 想象一个大水池里有N多还未排好的序列的氢气球，较大的先冒出来，然后依次是较小的往上冒。即，每次比较相邻的两个数，小的在前大的在后，否则进行位置互换。
代码实现：（举例几种写法，注意循环体的判断条件）建议使用第一、二种。
~~~
/**
* 交换方法
* @param array $arr 目标数组
* @param $a 索引a
* @param $b 索引b
* @param bool $flag 交换标志
* @return bool
*/
function swap(array &$arr,$a,$b,$flag = false){
// 遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡
if($arr[$a] > $arr[$b]){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
$flag = true;
}
return $flag;
}
/**
* 第一种写法
* @param $arr 所要排序的数组
* @return mixed 返回的数组
*/
function bubbleSort($arr) {
$len = count($arr);
if ($len <= 1) {return $arr;}
//该层循环控制 需要冒泡的轮数
for ($i = 0; $i < $len-1; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($j = $i + 1; $j < $len; $j++) {
// 或者 $this->swap($arr,$j,$j+1);
$this->swap($arr,$i,$j);
}
}
return $arr;
}
//第二种写法
public function BubbleSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0;$i < $len-1;$i++){
//TODO 本趟排序开始前，交换标志应为假
$flag = false;
for ($j = 0;$j <= $len-2;$j++){
$flag = $this->swap($arr,$j,$j+1,$flag);
}
if(!$flag) return $arr;
}
return $arr;
}
//第三种写法
function BubbleSort3(array &$arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++){
//从后往前逐层上浮小的元素 $j >= 0
for($j = $len - 2;$j >= $i ;$j --){
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
//第四种写法
function bubbleSort4($arr)
{
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++) {
for($j = 0;$j < $len-$i-1;$j++) {
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
~~~
小结：
> 时间复杂度：O(n^2)
> 补充：可使用PHP内置函数 sort()或rsort().
> 上述函数对索引数组按照键值进行排序，为 array 中的单元赋予新的键名，这将删除原有的键名而不仅是重新排序。如果成功则返回 TRUE，否则返回 FALSE
# 【二】.选择排序
思路分析：
> 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
代码实现
~~~
/*
* @param 选择排序法
* 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
* */
function selectSort($arr){
//双重循环完成，外层控制轮数，内层控制比较次数
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0; $i < $len-1; $i++) {
$minIndex = $i;
// 找出i后面最小的元素与当前元素交换
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$minIndex] > $arr[$j]){
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
~~~
小结：
> 时间复杂度：O(n^2)
> 不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
> 在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了
> 最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快
>
# 【三】.插入排序
思路分析：
> 每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。(从而得到一个新的、个数加一的有序数据)
描述：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤 2~5
代码实现
~~~
/*
* 插入排序法
* 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
* */
function insertSort($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是准备插入的数
$insertIndex = $i - 1; //有序表中准备比较的数的下标
while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
$arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
$insertIndex--; //将下标往前挪，准备与前一个进行比较
}
if($insertIndex + 1 !== $i){
$arr[$insertIndex + 1] = $insertVal;
}
}
}
return $arr;
}
function insertSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默认$array[0]，已经有序，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是准备插入的数
//$j 有序表中准备比较的数的下标
//$j-- 将下标往前挪，准备与前一个进行比较
for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
$arr[$j+1]= $arr[$j];//将数组往后挪
}
$arr[$j + 1] = $insertVal;
}
}
return $arr;
}
~~~
小结：
> 时间复杂度：O(n^2)
> 空间复杂度：O(1) (用于记录需要插入的数据)
> 稳定的排序方法
> 算法适用于少量数据的排序
> 如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
>
# 【四】.快速排序
思路分析：
> 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
> 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
>
代码实现
~~~
/**
* @param $arr 目标数组
* @param int $l 左起坐标
* @param $r 右起坐标 初始化传入数组时，$r = count($arr)-1
* @return mixed
*/
public function quick_sort(&$arr, $l=0, $r)
{
$length = count($arr);
//先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
if(!is_array($arr)||$length <= 1) {return $arr;}
if ($l < $r)
{
$i = $l;
$j = $r;
$baseVal = $arr[$l];
while ($i < $j)
{
// 从右向左找第一个小于$baseVal的数
while($i < $j && $arr[$j] >= $baseVal)
$j--;
if($i < $j)
$arr[$i++] = $arr[$j];
// 从左向右找第一个大于等于$baseVal的数
while($i < $j && $arr[$i] < $baseVal)
$i++;
if($i < $j)
$arr[$j--] = $arr[$i];
}
$arr[$i] = $baseVal;
$this->quick_sort($arr, $l, $i - 1); // 递归调用
$this->quick_sort($arr, $i + 1, $r);
return $arr;
}
}
/*
* 快速排序法
* */
public function quick_sort2($arr) {
$length = count($arr);
//先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
if(!is_array($arr)||$length <= 1) {return $arr;}
//选择第一个元素作为基准
$baseValue = $arr[0];
//遍历除了标尺外的所有元素，按照大小关系放入两个数组内
//初始化两个数组
$leftArr = array(); //小于基准的
$rightArr = array(); //大于基准的
//使用for循环进行遍历，把选定的基准当做比较的对象
for($i = 1; $i<$length; $i++) {
if( $arr[$i] < $baseValue) {
//放入左边数组
$leftArr[] = $arr[$i];
} else {
//放入右边数组
$rightArr[] = $arr[$i];
}
}
//再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
$leftArr = $this->quick_sort2($leftArr);
$rightArr = $this->quick_sort2($rightArr);
//合并 左边 标尺 右边， 注意：array($baseValue),关联着重复数据
return array_merge($leftArr, array($baseValue), $rightArr);
}
~~~
小结：
> 既不浪费空间又可以快一点的排序算法
> 最差时间复杂度O(N^2)，平均时间复杂度为O(NlogN)
>
# 【五】.计数排序
思路分析
> 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序
算法描述：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
代码实现
~~~
/**
* 计数排序
* @param $arr
* @return array
*/
function countingSort($arr)
{
$len = count( $arr );
if( $len <= 1 ) return $arr;
// 找出待排序的数组中最大值和最小值
$min = min($arr);
$max = max($arr);
// 计算待排序的数组中每个元素的个数
$countArr = array();
for($i = $min; $i <= $max; $i++)
{
$countArr[$i] = 0;
}
foreach($arr as $v)
{
$countArr[$v] += 1;
}
$resArr = array();
foreach ($countArr as $k=>$c) {
for($i = 0; $i < $c; $i++)
{
$resArr[] = $k;
}
}
return $resArr;
}
~~~
小结：
> 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
> 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
> 计数排序不是比较排序，排序的速度快于任何比较排序算法
> 最佳情况：T(n) = O(n+k)
> 最差情况：T(n) = O(n+k)
> 平均情况：T(n) = O(n+k)
>
# 【六】.桶排序
思路分析
> 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
算法描述
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
代码实现
~~~
/**
* 木桶排序设计
* @param $arr 目标数组
* @param int $bucketCount 分配的木桶数目（整数）
* @return array
*/
public function bucketSort($arr,$bucketCount = 10)
{
$len = count($arr);
$max = max($arr)+1;
if ($len <= 1) {return $arr;}
//填充木桶
$arrFill = array_fill(0, $bucketCount, []);
//开始标示木桶
for($i = 0; $i < $len ; $i++)
{
$key = intval($arr[$i]/($max/$bucketCount));
array_push($arrFill[$key] , $arr[$i]);
//TODO 测试发现：如果此处调用，耗时翻倍
/*if(count($arrFill[$key])){
$arrFill[$key] = $this->insertSort($arrFill[$key]);
}*/
}
//对每个不是空的桶进行排序
foreach ($arrFill as $key=>$f){
if (count($f)){
$arrFill[$key] = $this->insertSort($f);
}
}
//开始从木桶中拿出数据
for($i = 0; $i < count($arrFill); $i ++)
{
if($arrFill[$i]){
for($j = 0; $j <= count($arrFill[$i]); $j++)
{ //这一行主要用来控制输出多个数字
if ($arrFill[$i][$j]){
$arrBucket[] = $arrFill[$i][$j];
}
}
};
}
return $arrBucket;
}
~~~
> 上述代码是我根据对木桶排序的定义进行的设计，因为网上多数的PHP代码感觉不合规范，其中的insertSort()为借用的文中所写的插入排序
> 通过测试发现，此方法耗时比countingSort()要长好多，此处仅做参考不做推荐。
>
总结：
> 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
> 稳定的排序方法
> 桶排序是计数排序的升级版
> 最佳情况：T(n) = O(n+k)
> 最差情况：T(n) = O(n^2)
> 平均情况：T(n) = O(n+k)
- 序言
- 基础知识
- thinkphp基础知识
- Thinkphp5CURD
- 数据库创建
- 数据库删除
- 数据库更新
- 数据库查询
- thinkphp5控制器
- 空操作空控制器
- 控制器基类
- 请求信息
- 行为和钩子
- thinkphp5路由设置
- 变量路由
- 常用方法清单
- 环境搭建
- lnmp
- 升级php
- window环境
- Thinkphp小案例
- 分类管理
- 数据库设计
- 模型
- 控制器
- 视图
- 文件上传
- 上传接口
- 视图
- 表单提交
- 视图设计
- 控制器
- 权限控制
- 案例解释说明
- 登录验证
- Laravel5.3登录模式
- redis使用
- 一键安装
- 程序设计与实现
- 页面设计
- 功能设计
- 安装功能实际
- 函数库
- 配置文件
- 清除缓存
- 状态值修改
- 数据库备份还原
- controller.php
- common.php
- index.html
- importlist.html
- 完整的增删查改
- 查询语句
- 多语言支持
- JpGraph图表类库
- 微信支付
- payBase.php
- Order.php
- Oauth.php
- Jspay.php
- 下载远程地址中的图片
- URL重写隐藏入口文件
- 图片水印
- 整合百度编辑器
- Ueditor
- ueditor完整配置项
- 配置信息常见的方式
- HTTP 断点续传（PHP实现）
- layui.upload上传文件或图片
- QQ微信域名防封 预防域名封禁 强制跳转至浏览器
- 蜘蛛篇
- 超简单实现php谷歌验证
- 采集金山词霸每日一句
- think-swoole
- 原生PHP小案例
- 查询修改数据库
- mysql支付回调源码
- pdo连接微信退款
- 前端小案例
- html快捷查询
- layui经验总结
- layui 表单增强插件
- Vue列表Ajax实战教程
- PHP基础
- 类的自动载入
- php基础函数- 字符串函数
- php基础函数-数学函数
- php基础函数-数组函数
- PHP常见排序算法学习
- 请求第三方
- 从网络下载文件
- 检查网站是否宕机
- file_get_contents
- 算法
- php 抽奖算法（适合九宫格和大转盘）
- 自己动手丰衣足食
- 入口文件
- start.php
- app.php
- load.php
- route.php
- JqHttp
- Jqfile
- Jqutil
- pdo连接数据库类
- 常见的php类
- php数据接口类
- 生成多层树状下拉选框的工具模型
- 上传下载类
- 微信用户相关类
- Zip压缩类
- 列表树生成工具类
- 日期时间操作类
- 文件及文件夹处理类
- 字符串处理类
- php守护进程类
- RSA算法类
- php支持中英文的加密解密类
- CURL多线程请求
- 通用数据库操作类
- 缓存类
- cookie类
- 常见的验证方法
- 随机密钥
- 日志Log
- php-redis 操作类 封装
- OpensslRsa 加密、解密、签名、验签类
- 模板输出类
- 发送邮件
- 封装的mysqli类
- PHP时间段分割类库
- PHP apk解包识版本号信息和ipa包信息
- 访问客户端信息
- http请求
- PHP 无数据库读写配置文件
- 自己动手写一个jwt类
- php实现对图片对称加解密（适用身份证加密等场景）
- 常见php函数
- 无限分类
- 获取文章图片
- 加密解密
- JSON数据输出（适合在tp中）
- 删除目录和文件
- 判断是否为手机访问
- 获取客户端真实IP
- 随机生成ip地址
- 字符串与二进制进行转换
- 对数组进行排序
- 格式化字节大小
- 时间戳格式化
- 获取数据的所有子孙数据的id值
- 取得视频文件的缩略图
- 图片裁剪函数
- 按照每过0:00算一天
- 下载文件
- PHP随机密码生成
- 判断数字大小
- 报文组成
- 通过ip定位城市
- PDO方式连接MySQL数据库
- 数组与xml
- php字符串处理函数
- 判断是否ajax提交
- 生成概率,用于抽奖
- 断点续传
- PHP使用星号替代用户名手机和邮箱
- 获取毫秒级别的时间戳
- php日志函数
- 随机颜色生成器
- 时间差异计算函数
- 黑名单过滤
- 常见PHP 正则表达式
- php获取浏览器类型
- 邮件发送
- 获取qq昵称
- 正则获取手机号归属地
- 判断是否是移动客户端 移动设备
- gbk和utf8编码自动识别方法
- 人性化时间显示
- 请求API接口
- 数据库备份
- PHP并发下安全读写文件函数
- PHP读取exe软件版本号
- PHP为任意页面设置访问密码
- PHP利用百度当图床
- 秒/分钟/小时前
- 常见的js函数
- 短信验证函数
- 上下收缩菜单
- jQuery 树插件zTree
- 页面刷新跳转
- jquery导出报表
- js实现定时效果
- 获取当前经纬度
- JQuery实现图片大小自适应
- 网站运行时间
- 判断浏览器类型
- 百度推送
- js对指定数据进行排序
- 常见工具方法
- JSPinyin
- 技术相关文章
- 高级PHP工程师所应该具备哪些技能
- 最简洁的PHP程序员学习路线及建议
- 优化PHP代码的一些建议
- TP5性能优化建议
- 程序猿专用代码注释:佛祖保佑，永无BUG
- 一组匹配中国大陆手机号码的正则表达式
- Apache/Nginx/PHP服务器反爬虫代码大全
- 番外
- 配置shadowsocks服务端
- python
- go
- 如何在1分钟内黑掉任何网站！
- 百度贴吧敏感词
- 贴吧手工养号发帖教程
- 搞笑的注释代码
- Heroku