php快速排序原理与实现方法分析

本文实例讲述了php快速排序方法。分享给大家供大家参考,具体如下:

<?php
$n = array('13','14','55','10','54','2','79','106','89','90','22','60','111','77777','-110','-10','123');
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;
2)、以第一个数组元素作为关键数据,赋值给X,即X:=A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I=J;

快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列

补充:小编在这里推荐一款本站的php格式化美化的排版工具帮助大家在以后的PHP程序设计中进行代码排版:

php代码在线格式化美化工具:

http://tools.jb51.net/code/phpformat

另外,由于php属于C语言风格,因此下面这款工具同样可以实现php代码的格式化:

C语言风格/HTML/CSS/json代码格式化美化工具:
http://tools.jb51.net/code/ccode_html_css_json

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数组(Array)操作技巧大全》、《php排序算法总结》、《PHP常用遍历算法与技巧总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数学运算技巧总结》、《php正则表达式用法总结》、《PHP运算与运算符用法总结》、《php字符串(string)用法总结》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

时间: 2016-05-25

php项目开发中用到的快速排序算法分析

本文实例讲述了php项目开发中用到的快速排序算法.分享给大家供大家参考,具体如下: 实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算法),另外,每种语言,比如java,php都或多或少已经封装好排序函数给程序员使用.比如有个共识,大家做web开发的基本都明白,业务逻辑多比较简单,不是很复杂的业务逻辑.我们作为web开发的程序员,基本是是web架构,对数据库增删查改数据,然后把数据展示在页面中,大多

php数据结构与算法(PHP描述) 快速排序 quick sort

复制代码 代码如下: <?php /** * 快速排序 quick sort * **/ function sort_quick($arrData) { if(empty($arrData) || !is_array($arrData)) return false; $flag = $arrData[0]; $len = count($arrData) - 1; if($len == 0) return $arrData; // 如果只有一个数据的数组直接返回 $arrLeft = array(

php实现快速排序的三种方法分享

写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法.三组算法实现和比较如下: 方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数.在三种方法中效率最低.最坏情况下算法退化为(O(n*n)) 复制代码 代码如下: function quick_sort($array) { if(count($array) <= 1) return $array; $key = $array[0]

PHP两种快速排序算法实例

虽然在PHP这样的web应用开发中,我们不是太强调排序的重要性,因为PHP自身已经带了例如sort()等这样强大的排序函数,但是在一些重要的场合,例如某些高并发的场合,我想排序算法的影响已经不能忽略.所以在此介绍递归排序和迭代排序. 递归法: /** * 递归法实现的快速排序 */ function quicksort($seq) { $k = $seq[0]; $x = array(); $y = array(); for($i=1; $i< $_size; $i++) { if($seq[$

php实现快速排序法函数代码

代码1: 复制代码 代码如下: <?php function quicksort($str){ if(count($str)<=1) return $str;//如果个数不大于一,直接返回 $key=$str[0];//取一个值,稍后用来比较: $left_arr=array(); $right_arr=array(); for($i=1;$i<count($str);$i++){//比$key大的放在右边,小的放在左边: if($str[$i]<=$key) $left_arr[

php排序算法(冒泡排序,快速排序)

冒泡排序实现原理 ① 首先将所有待排序的数字放入工作列表中.② 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换. ③ 重复步骤②,直至再也不能交换. 代码实现 复制代码 代码如下: <?php function bubbingSort(array $array) {     for($i=0, $len=count($array)-1; $i<$len; ++$i)     {         for($j=$len; $j>$i;

PHP快速排序quicksort实例详解

本文实例讲述了PHP快速排序quicksort.分享给大家供大家参考,具体如下: quicksort 在快速排序算法中,使用了分治策略.首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束.(即一分为二的思想) 步骤如下: 在序列中选择一个关键元素做为轴: 对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面.在进行划分之后,轴便在它最终的位置上: 递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列. 比如序列$arr: 5 3 0

php冒泡排序、快速排序、快速查找、二维数组去重实例分享

一.冒泡排序 复制代码 代码如下: //冒泡排序function bubble_sort($array){    $count=count($array);    if($count <= 0){        return false;    }    for($i=0;$i<$count;$i++){        for($j=0;$j<$count-$i-1;$j++){            if( $array[$j] > $array[$j+1] ){        

php冒泡排序与快速排序实例详解

本文实例分析了php冒泡排序与快速排序算法.分享给大家供大家参考,具体如下: $a=array('3','8','1','4','11','7'); print_r($a); $len = count($a); //从小到大 for($i=1;$i<$len;$i++) { for($j=$len-1;$j>=$i;$j--) if($a[$j]<$a[$j-1]) {//如果是从大到小的话,只要在这里的判断改成if($b[$j]>$b[$j-1])就可以了 $x=$a[$j];

PHP 快速排序算法详解

概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现 复制代码 代码如下: /*     快速排序 */ function quickSort($array) {    

php关联数组快速排序的方法

本文实例讲述了php关联数组快速排序的方法.分享给大家供大家参考.具体如下: <?php function qsort($a,$f) { qsort_do(&$a,0,Count($a)-1,$f); } function qsort_do($a,$l,$r,$f) { if ($l < $r) { qsort_partition(&$a,$l,$r,&$lp,&$rp,$f); qsort_do(&$a,$l,$lp,$f); qsort_do(&am

php简单实现快速排序的方法

本文实例讲述了php简单实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: function quicksort($seq) { if(!count($seq)) return $seq; $k = $seq[0]; $x = $y = array(); for($i=count($seq); --$i;) { if($seq[$i] <= $k) { $x[] = $seq[$i]; } else { $y[] = $seq[$i]; } } return array_merge(q

JS插入排序简单理解与实现方法分析

本文实例讲述了JS插入排序简单理解与实现方法.分享给大家供大家参考,具体如下: 在这里,我详细的讲一下我个人对于插入排序的理解. 每个人对于事物的理解都是不一样的,因为每个人对世界万物的看法和思考方式都不一样.因此,对于排序算法,我想每个人都有自己的理解方式,所以,虽然博客园里有很多关于排序的文章,但那只是其他人对这几个排序的理解方式,而笔者也有自己的理解方式,所以,笔者也就没有在意博客园写了那么多关于排序的文章而还在这里写下个人的见解了. 对于插入排序,笔者是这么理解的: 插入排序就是把一组数

JS桶排序的简单理解与实现方法示例

本文实例讲述了JS桶排序的简单理解与实现方法.分享给大家供大家参考,具体如下: 桶排序,利用编号分组存储数字,再利用编号合并分组的一种算法排序. 举个易于理解的例子: 一组数字,9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14 我们把这组数字分组编号成10个桶装起来,但怎么编号分组呢? 这里我们利用数字范围来对数字进行分桶.首先,最大数减去最小数,获取这组数字的取值范围,然后,我们让这个取值范围除以桶数,获取一个桶的取值范围,既然知道一个桶的取值

php简单复制文件的方法

本文实例讲述了php简单复制文件的方法.分享给大家供大家参考,具体如下: <?php /** *author:果冻 *qq:52091199 *wyg517.blog.163.com **/ $file = 'image/a1.jpg'; $newfile = 'a/123.jpg'; //必须有写入权限 if (file_exists($file) == false) { die ('文件不在,无法复制'); } $result = copy($file, $newfile); if ($re

Python使用shelve模块实现简单数据存储的方法

本文实例讲述了Python使用shelve模块实现简单数据存储的方法.分享给大家供大家参考.具体分析如下: Python的shelve模块提供了一种简单的数据存储方案,以dict(字典)的形式来操作数据. #!/usr/bin/python import sys, shelve def store_person(db): """ Query user for data and store it in the shelf object """ pi

python根据出生年份简单计算生肖的方法

本文实例讲述了python根据出生年份简单计算生肖的方法.分享给大家供大家参考.具体分析如下: 这里使用python根据出生年份计算生肖,看了代码会发现原来这么简单 #计算生肖 def ChineseZodiac(year): return u'猴鸡狗猪鼠牛虎兔龙蛇马羊'[year%12] ChineseZodiac(1990) 希望本文所述对大家的Python程序设计有所帮助.

jQuery简单创建节点的方法

本文实例讲述了jQuery简单创建节点的方法.分享给大家供大家参考,具体如下: <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title></title> <script type="text/javascript" src="js/jquery-1

GO语言实现简单TCP服务的方法

本文实例讲述了GO语言实现简单TCP服务的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import ( "net" "fmt" ) var (   maxRead = 1100     msgStop   = []byte("cmdStop")     msgStart  = []byte("cmdContinue")     ) func main() {       ho

JS+CSS简单树形菜单实现方法

本文实例讲述了JS+CSS简单树形菜单实现方法.分享给大家供大家参考.具体如下: 这是一款不错的CSS树形菜单,树状列表,当然不全是CSS实现,部分功能还使用了JavaScript代码进行配合,删减了修饰用的菜单图片,大家用的时候自己图片加进去,IMG标签大部分都预留了出来,稍懂Html语法的朋友很容易就看懂的. 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/js-css-simple-tree-menu-style-codes/ 具体代码如下

JS实现简单路由器功能的方法

本文实例讲述了JS实现简单路由器功能的方法.分享给大家供大家参考.具体实现方法如下: var wawa = {}; wawa.Router = function(){ function Router(){ } Router.prototype.setup = function(routemap, defaultFunc){ var that = this, rule, func; this.routemap = []; this.defaultFunc = defaultFunc; for (v