很多站长朋友们都不太清楚快速排序php实现，今天小编就来给大家整理快速排序php实现，希望对各位有所帮助，具体内容如下：
本文目录一览： 1、 PHP快速排序算法实现的原理及代码详解 2、 PHP实现常见排序 3、 php几种排序算法实例详解 4、 PHP实现常见的排序算法 5、 thinkphp如何实现快速排序 6、 php快速排序算法 PHP快速排序算法实现的原理及代码详解算法原理
下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
function
quickSort($arr)
{
$len
=
count($arr);
if
($len
<=
1)
{
return
$arr;
}
$v
=
$arr[0];
$low
=
$up
=
array();
for
($i
=
1;
$i
<
$len;
++$i)
{
if
($arr[$i]
>
$v)
{
$up[]
=
$arr[$i];
}
else
{
$low[]
=
$arr[$i];
}
}
$low
=
quickSort($low);
$up
=
quickSort($up);
return
array_merge($low,
array($v),
$up);
}
测试代码:
$startTime
=
microtime(1);
$arr
=
range(1,
10);
shuffle($arr);
echo
"before
sort:
",
implode(',
',
$arr),
"\n";
$sortArr
=
quickSort($arr);
echo
"after
sort:
",
implode(',
',
$sortArr),
"\n";
echo
"use
time:
",
microtime(1)
-
$startTime,
"s\n";
测试结果:
before
sort:
1,
7,
10,
9,
6,
3,
2,
5,
4,
8
after
sort:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
use
time:
0.0009009838104248s
时间复杂度
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
1)
为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
2)
为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
您可能感兴趣的文章:PHP快速排序算法实例分析PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】PHP排序算法之快速排序(Quick
Sort)及其优化算法详解PHP递归实现快速排序的方法示例php
二维数组快速排序算法的实现代码PHP常用排序算法实例小结【基本排序，冒泡排序，快速排序，插入排序】PHP快速排序quicksort实例详解
PHP实现常见排序//插入排序（一维数组） function insert_sort($arr){ $count = count($arr); for($i= ; $i<$count; $i++){ $tmp = $arr[$i]; $j = $i ; while($arr[$j] > $tmp){ $arr[$j+ ] = $arr[$j]; $arr[$j] = $tmp; $j ; } } return $arr; } //选择排序（一维数组） function select_sort($arr){ $count = count($arr); for($i= ; $i<$count; $i++){ $k = $i; for($j=$i+ ; $j<$count; $j++){ if ($arr[$k] > $arr[$j]) $k = $j; if ($k != $i){ $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; } } } return $arr; } //冒泡排序（一维数组） function bubble_sort($array){ $count = count($array); if ($count <= ) return false; for($i= ; $i<$count; $i++){ for($j=$count ; $j>$i; $j ){ if ($array[$j] < $array[$j ]){ $tmp = $array[$j]; $array[$j] = $array[$j ]; $array[$j ] = $tmp; } } } return $array; } //快速排序（一维数组） function quick_sort($array){ if (count($array) <= ) return $array; $key = $array[ ]; $left_arr = array(); $right_arr = array(); for ($i= ; $i<count($array); $i++){ if ($array[$i] <= $key) $left_arr[] = $array[$i]; else $right_arr[] = $array[$i]; } $left_arr = quick_sort($left_arr); $right_arr = quick_sort($right_arr); return array_merge($left_arr array($key) $right_arr); } lishixinzhi/Article/program/PHP/201311/21194
php几种排序算法实例详解四种排序算法的PHP实现：
1) 插入排序(Insertion Sort)的基本思想是：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
2) 选择排序(Selection Sort)的基本思想是：
每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
3) 冒泡排序的基本思想是：
两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
4) 快速排序实质上和冒泡排序一样，都是属于交换排序的一种应用。所以基本思想和上面的冒泡排序是一样的。
1. sort.php文件如下：
<?php
class Sort {
private $arr = array();
private $sort = 'insert';
private $marker = '_sort';
private $debug = TRUE;
/**
* 构造函数
*
* @param array 例如：
$config = array (
'arr' => array(22,3,41,18) , //需要排序的数组值
'sort' => 'insert', //可能值: insert, select, bubble, quick
'debug' => TRUE //可能值: TRUE, FALSE
)
*/
public function construct($config = array()) {
if ( count($config) > 0) {
$this->_init($config);
}
}
/**
* 获取排序结果
*/
public function display() {
return $this->arr;
}
/**
* 初始化
*
* @param array
* @return bool
*/
private function _init($config = array()) {
//参数判断
if ( !is_array($config) OR count($config) == 0) {
if ($this->debug === TRUE) {
$this->_log("sort_init_param_invaild");
}
return FALSE;
}
//初始化成员变量
foreach ($config as $key => $val) {
if ( isset($this->$key)) {
$this->$key = $val;
}
}
//调用相应的成员方法完成排序
$method = $this->sort . $this->marker;
if ( ! method_exists($this, $method)) {
if ($this->debug === TRUE) {
$this->_log("sort_method_invaild");
}
return FALSE;
}
if ( FALSE === ($this->arr = $this->$method($this->arr)))
return FALSE;
return TRUE;
}
/**
* 插入排序
*
* @param array
* @return bool
*/
private function insert_sort($arr) {
//参数判断
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this->debug === TRUE) {
$this->_log("sort_array(insert)_invaild");
}
return FALSE;
}
//具体实现
$count = count($arr);
for ($i = 1; $i < $count; $i++) {
$tmp = $arr[$i];
for($j = $i-1; $j >= 0; $j--) {
if($arr[$j] > $tmp) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
return $arr;
}
/**
* 选择排序
*
* @param array
* @return bool
*/
private function select_sort($arr) {
//参数判断
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this->debug === TRUE) {
$this->_log("sort_array(select)_invaild");
}
return FALSE;
}
//具体实现
$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 ($min != $i) {
$tmp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
/**
* 冒泡排序
*
* @param array
* @return bool
*/
private function bubble_sort($arr) {
//参数判断
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this->debug === TRUE) {
$this->_log("sort_array(bubble)_invaild");
}
return FALSE;
}
//具体实现
$count = count($arr);
for ($i = 0; $i < $count; $i++) {
for ($j = $count-1; $j > $i; $j--) {
if ($arr[$j] < $arr[$j-1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $tmp;
}
}
}
return $arr;
}
/**
* 快速排序
* @by
* @param array
* @return bool
*/
private function quick_sort($arr) {
//具体实现
if (count($arr) <= 1) return $arr;
$key = $arr[0];
$left_arr = array();
$right_arr = array();
for ($i = 1; $i < count($arr); $i++){
if ($arr[$i] <= $key)
$left_arr[] = $arr[$i];
else
$right_arr[] = $arr[$i];
}
$left_arr = $this->quick_sort($left_arr);
$right_arr = $this->quick_sort($right_arr);
return array_merge($left_arr, array($key), $right_arr);
}
/**
* 日志记录
*/
private function _log($msg) {
$msg = 'date[' . date('Y-m-d H:i:s') . '] ' . $msg . '\n';
return @file_put_contents('sort_err.log', $msg, FILE_APPEND);
}
}
/*End of file sort.php*/
/*Location htdocs/sort.php */
2. sort_demo.php文件如下：
<?php
require_once('sort.php');
$config = array (
'arr' => array(23, 22, 41, 18, 20, 12, 200303,2200,1192) ,
//需要排序的数组值
'sort' => 'select',
//可能值: insert, select, bubble, quick
'debug' => TRUE
//可能值: TRUE, FALSE
);
$sort = new Sort($config);
//var_dump($config['arr']);
var_dump($sort->display());
/*End of php*/
PHP实现常见的排序算法注：为方便描述，下面的排序全为正序（从小到大排序）
假设有一个数组[a,b,c,d]
冒泡排序依次比较相邻的两个元素，如果前面的元素大于后面的元素，则两元素交换位置；否则，位置不变。具体步骤：
1，比较a,b这两个元素，如果a>b,则交换位置，数组变为：[b,a,c,d]
2，比较a,c这两个元素，如果a<c,则位置不变，数组变为：[b,a,c,d]
3，比较c,d这两个元素，如果c>d,则交换位置，数组变为：[b,a,d,c]
完成第一轮比较后，可以发现最大的数c已经排（冒）在最后面了，接着再进行第二轮比较，但第二轮比较不必比较最后一个元素了，因为最后一个元素已经是最大的了。
第二轮比较结束后，第二大的数也会冒到倒数第二的位置。
依次类推，再进行第三轮，，，
就这样最大的数一直往后排（冒），最后完成排序。所以我们称这种排序算法为冒泡排序。
选择排序是一种直观的算法，每一轮会选出列中最小的值，把最小值排到前面。具体步骤如下:
插入排序步骤大致如下：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
步骤：
从数列中挑出一个元素，称为 “基准”（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
thinkphp如何实现快速排序thinkphp使用的数据库是mysql，mysql多个字段排序的语句：
select
* from `表名` where 条件 order by 字段1 desc,字段2
asc,...
thinkphp中排序方法为
$User->where('score>0')->order('score desc')....;
但是例子中只能单字段排序，不过可以理解成字符串，那就可以这样写试试
$User->where('score>0')->order('score desc,id asc,...')....;
php快速排序算法<?php
function quick_sort($arr) {
// 判断是否需要继续
if (count($arr) <= 1) {
return $arr;
}
$middle = $arr[0]; // 中间值
$left = array(); // 小于中间值
$right = array();// 大于中间值
// 循环比较
for ($i=1; $i < count($arr); $i++) {
if ($middle < $arr[$i]) {
// 大于中间值
$right[] = $arr[$i];
} else {
// 小于中间值
$left[] = $arr[$i];
}
}
// 递归排序两边
$left = quick_sort($left);
$right = quick_sort($right);
// 合并排序后的数据，别忘了合并中间值
return array_merge($left, array($middle), $right);
}
$arr = array(25,133,452,364,5876,293,607,365,8745,534,18,33);
echo '<pre>';
var_dump($arr);
var_dump(quick_sort($arr));
关于快速排序php实现的介绍到此就结束了，不知道本篇文章是否对您有帮助呢？如果你还想了解更多此类信息，记得收藏关注本站，我们会不定期更新哦。
查看更多关于快速排序php实现 php快排算法的详细内容...