7种php基本排序实现方法
更新时间:2016年3月17日 10:11 点击:1847
本文总结了一下常用的7种排序方法,并用php语言实现。
1、直接插入排序
/* * 直接插入排序,插入排序的思想是:当前插入位置之前的元素有序, * 若插入当前位置的元素比有序元素最后一个元素大,则什么也不做, * 否则在有序序列中找到插入的位置,并插入 */ function insertSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { if($arr[$i-1] > $arr[i]) { for($j = $i - 1;$j >= 0; $j-- ) { $tmp = $arr[$j+1]; if($tmp < $arr[$j]) { $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; }else{ break; } } } } return $arr; }
2、冒泡排序
/* 冒泡排序,冒泡排序思想:进行 n-1 趟冒泡排序, 每趟两两比较调整最大值到数组(子数组)末尾 */ function bubbleSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { for($j = 0; $j < $len-$i; $j++) { if($arr[$j] > $arr[$j+1]) { $tmp = $arr[$j+1]; $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; } } } return $arr; }
3、简单选择排序
/* 简单选择排序, 简单排序思想:从数组第一个元素开始依次确定从小到大的元素 */ function selectSort($arr) { $len = count($arr); for($i = 0; $i < $len; $i++) { $k = $i; for($j = $i+1; $j < $len; $j++) { if($arr[$k] > $arr[$j]) { $k = $j; } } if($k != $i) { $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; } } return $arr; }
4、希尔排序
/* 希尔排序,希尔排序原理:将数组按指定步长分隔成若干子序列,然后分别对子序列进行排序(在这是直接) */ function shellSort($arr) { $len = count($arr); $k = floor($len/2); while($k > 0) { for($i = 0; $i < $k; $i++) { for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) { if($arr[$j] > $arr[$j+$k]) { $tmp = $arr[$j+$k]; $arr[$j+$k] = $arr[$j]; $arr[$j] = $tmp; } } } $k = floor($k/2); } return $arr; }
5、快速排序
/* * 快速排序,快排思想:通过一趟排序将待排的记录分为两个独立的部分,其中一部分的记录的关键字均不大于 * 另一部分记录的关键字,然后再分别对这两部分记录继续进行快速排序,以达到整个序列有序,具体做法需要 * 每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。 * quickSort($arr, 0, count($arr) -1); */ function quickSort(&$arr,$low,$high) { if($low < $high) { $i = $low; $j = $high; $primary = $arr[$low]; while($i < $j) { while($i < $j && $arr[$j] >= $primary) { $j--; } if($i < $j) { $arr[$i++] = $arr[$j]; } while($i < $j && $arr[$i] <= $primary) { $i++; } if($i < $j) { $arr[$j--] = $arr[$i]; } } $arr[$i] = $primary; quickSort($arr, $low, $i-1); quickSort($arr, $i+1, $high); } }
6、堆排序
/* 堆排序 */ // 调整子堆的为大根堆的过程,$s为子堆的根的位置,$m为堆最后一个元素位置 function heapAdjust(&$arr, $s, $m) { $tmp = $arr[$s]; // 在调整为大根堆的过程中可能会影响左子堆或右子堆 // for循环的作用是要保证子堆也是大根堆 for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) { // 找到根节点的左右孩子中的最大者,然后用这个最大者与根节点比较, // 若大则进行调整,否则符合大根堆的 特点跳出循环 if($j < $m && $arr[$j] < $arr[$j+1]) { $j++; } if($tmp >= $arr[$j] ) { break; } $arr[$s] = $arr[$j]; $s = $j; } $arr[$s] = $tmp; } // 堆排序 function heapSort($arr) { $len = count($arr); // 依次从子堆开始调整堆为大根堆 for($i = floor($len/2-1); $i >= 0; $i--) { heapAdjust($arr, $i, $len-1); } // 依次把根节点调换至最后一个位置,再次调整堆为大根堆,找到次最大值, // 依次类推得到一个有序数组 for($n = $len-1; $n > 0; $n--) { $tmp = $arr[$n]; $arr[$n] = $arr[0]; $arr[0] = $tmp; heapAdjust($arr, 0, $n-1); } return $arr; }
7、归并排序
/* 归并排序,这里实现的是两路归并 */ // 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n] function Merge(&$arr1, &$arr2, $s, $m, $n) { for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) { if($arr1[$i]<$arr1[$j]) { $arr2[$k] = $arr1[$i++]; }else { $arr2[$k] = $arr1[$j++]; } } if($i <= $m) { for(; $i <= $m; $i++) { $arr2[$k++] = $arr1[$i]; } } else if($j <= $n) { for(; $j <= $n; $j++) { $arr2[$k++] = $arr1[$j]; } } } // 递归形式的两路归并 function MSort(&$arr1, &$arr2, $s, $t) { if($s == $t) { $arr2[$s] = $arr1[$s]; }else { $m = floor(($s+$t)/2); $tmp_arr = array(); MSort($arr1, $tmp_arr, $s, $m); MSort($arr1, $tmp_arr, $m+1, $t); Merge($tmp_arr, $arr2, $s, $m, $t); } } // 对一位数组$arr[0..n-1]中的元素进行两路归并 function mergeSort($arr) { $len = count($arr); MSort($arr, $arr, 0, $len-1); return $arr; }
使用经验
若排序的记录数目n较小时,可以采用直接插入排序和简单选择排序,当记录本身信息量较大时,用简单选择排序方法较好。
若待排序记录按关键字基本有序,适合采用直接插入排序和冒泡排序。
若n值较大时,可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。
以上就是本文的全部内容,希望对大家的学习有所帮助。
相关文章
- 这篇文章主要介绍了源码分析系列之json_encode()如何转化一个对象,对json_encode()感兴趣的同学,可以参考下...2021-04-22
- PHP去除html、css样式、js格式的方法很多,但发现,它们基本都有一个弊端:空格往往清除不了 经过不断的研究,最终找到了一个理想的去除html包括空格css样式、js 的PHP函数。...2013-08-02
- index.php怎么打开?初学者可能不知道如何打开index.php,不会的同学可以参考一下本篇教程 打开编辑:右键->打开方式->经文本方式打开打开运行:首先你要有个支持运行PH...2017-07-06
PHP中func_get_args(),func_get_arg(),func_num_args()的区别
复制代码 代码如下:<?php function jb51(){ print_r(func_get_args()); echo "<br>"; echo func_get_arg(1); echo "<br>"; echo func_num_args(); } jb51("www","j...2013-10-04- 这篇文章主要介绍了PHP编程 SSO详细介绍及简单实例的相关资料,这里介绍了三种模式跨子域单点登陆、完全跨单点域登陆、站群共享身份认证,需要的朋友可以参考下...2017-01-25
- 这篇文章主要介绍了PHP实现创建以太坊钱包转账等功能,对以太坊感兴趣的同学,可以参考下...2021-04-20
- 这篇文章主要为大家详细介绍了php微信公众账号开发之五个坑,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2016-10-02
ThinkPHP使用心得分享-ThinkPHP + Ajax 实现2级联动下拉菜单
首先是数据库的设计。分类表叫cate.我做的是分类数据的二级联动,数据需要的字段有:id,name(中文名),pid(父id). 父id的设置: 若数据没有上一级,则父id为0,若有上级,则父id为上一级的id。数据库有内容后,就可以开始写代码,进...2014-05-31- 这篇文章主要介绍了PHP如何通过date() 函数格式化显示时间,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-11-13
- 今天我给大家分享的是在不刷新页面的前提下,使用PHP+jQuery+Ajax实现多图片上传的效果。用户只需要点击选择要上传的图片,然后图片自动上传到服务器上并展示在页面上。...2015-03-15
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要介绍了golang与php实现计算两个经纬度之间距离的方法,结合实例形式对比分析了Go语言与php进行经纬度计算的相关数学运算技巧,需要的朋友可以参考下...2016-07-29
- 这篇文章主要介绍了PHP正则表达式过滤html标签属性的相关内容,实用性非常,感兴趣的朋友参考下吧...2016-05-06
- 这篇文章主要为大家详细介绍了php构造方法中析构方法在继承中的表现,感兴趣的小伙伴们可以参考一下...2016-04-15
- 这篇文章主要介绍了thinkPHP中多维数组的遍历方法,以简单实例形式分析了thinkPHP中foreach语句的使用技巧,需要的朋友可以参考下...2016-01-12
- 这篇文章主要介绍了PHP如何使用cURL实现Get和Post请求,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-11
- 经常看到有人踩在了PHP路径的坑上面了,感觉有必要来说说PHP中相对路径的一些坑,以及PHP中绝对路径的使用,下面一起来看看。 ...2016-08-24
- 这篇文章主要为大家详细介绍了php图片添加文字水印实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2016-03-17
- 这篇文章主要介绍了jQuery实现对无序列表的排序功能,涉及jQuery与javascript常见的文本操作函数与sort排序函数的相关使用方法,具有一定参考借鉴价值,需要的朋友可以参考下...2016-07-01
- 这篇文章主要介绍了php有序列表或数组中删除指定的值的实现代码,删除给定的值之后,得到一个新的有序列表,长度-1,下面是具体的实现方法...2021-08-22