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();
$arrRight = array();
$len_l = 0;
$len_r = 0;
for($i = 1; $i <= $len;$i++) {
if($arrData[$i] < $flag) {
$arrLeft[$len_l] = $arrData[$i]; // 小于的放左边
$len_l++;
} else {
$arrRight[$len_r] = $arrData[$i]; // 大于等于的放右边
$len_r++;
}
}

// 合并数组
$arrResult = array();
if($len_l) {
$arrLeft = sort_quick($arrLeft);
for($i = 0;$i <= $len_l - 1; $i++ ) {
$arrResult[$i] = $arrLeft[$i];
}
}
$arrResult[$len_l] = $flag;
$len_l++;
if($len_r) {
$arrRight = sort_quick($arrRight);
for($i = 0;$i <= $len_r - 1; $i++ ) {
$arrResult[$len_l] = $arrRight[$i];
$len_l++;
}
}
echo "== ",$flag," ==========================================<br/>";
echo "data : ",print_r($arrData),"<br/>";
echo "filter left: ",print_r($arrLeft),"<br/>";
echo "filter right: ",print_r($arrRight),"<br/>";
echo "return : ",print_r($arrResult),"<br/>";

return $arrResult;
}
//$list = array(4,3,2,1,5,7,3,7);
$list = array(4,51,6,73,2,5,9,33,50,3,4,6,1,4,67);
$list = sort_quick($list);
echo "<pre>";print_r($list);

赞 (0)

相关推荐

  • php堆排序（heapsort）练习

    复制代码 代码如下: <?//堆排序应用class heapsort  {    var $a;    function setarray($a)//取得数组      {        $this->a=$a;      }    function runvalue($b,$c)//$a 代表数组,$b代表排序堆,$c代表结束点,      {        while($b<$c)          {            $h1=2*$b;            $h2=(2*$

  • 关于PHP堆栈与列队的学习

    在PHP中数组常被当作堆栈(后进先出:LIFO)与队列(先进先出:FIFO)结构来使用.PHP提供了一组函数可以用于push与pop(堆栈)还有shift与unshift(队列)来操作数组元素.堆栈与列队在实践中应用非常广泛.我们可以先看下堆栈:  复制代码 代码如下: <?php   $arr = array();   array_push($arr,'aaa');   array_push($arr,'bbb');   $arr.pop();   print_r($arr);?> 如果你打

  • PHP常用排序算法实例小结【基本排序，冒泡排序，快速排序，插入排序】

    php三种基础算法:冒泡,插入和快速排序法 $array = array(2,3,5,6,9,8,1); //冒泡排序思想,前后元素比较 function sort_bulldle($array){ $num = count($array); for($i=0; $i<$num; $i++){ $tmp = $array[$i]; for ($j=$i-1; $j>=0; $j--) { if ($tmp < $array[$j]) { $arr[$j+1] = $arr[$j]; $a

  • PHP利用二叉堆实现TopK-算法的方法详解

    PHP利用二叉堆实现TopK-算法的方法详解

    前言 在以往工作或者面试的时候常会碰到一个问题,如何实现海量TopN,就是在一个非常大的结果集里面快速找到最大的前10或前100个数,同时要保证内存和速度的效率,我们可能第一个想法就是利用排序,然后截取前10或前100,而排序对于量不是特别大的时候没有任何问题,但只要量特别大是根本不可能完成这个任务的,比如在一个数组或者文本文件里有几亿个数,这样是根本无法全部读入内存的,所以利用排序解决这个问题并不是最好的,所以我们这里就用php去实现一个小顶堆来解决这个问题. 二叉堆 二叉堆是一种特殊的堆,二

  • php堆排序实现原理与应用方法

    本文实例讲述了php堆排序实现原理与应用方法.分享给大家供大家参考.具体分析如下: 这里以php作为描述语言较详细讲解堆排序原理,因保证程序可读性,故不做优化,php程序中关于堆的一些概念如下: 假设n为当前数组的key则,n的父节点为 n>>1 或者 n/2(整除);n的左子节点l= n<<1 或 l=n*2,n的右子节点r=(n<<1)+1 或 r=l+1 $arr=array(1,8,7,2,3,4,6,5,9); 数组$arr的原形态结构如下: 1       

  • PHP中使用数组实现堆栈数据结构的代码

    在堆栈中,最后压入的数据(进栈),将会被最先弹出(出栈). 即在数据存储时采用"先进后出"的数据结构. PHP中,将数组当做一个栈,主要是使用array_push()和array_pop()两个系统函数来完成. 入栈主要是利用array_push()函数向第一个参数的数组尾部添加一个或多个元素,然后返回新数组的长度,示例如下: 复制代码 代码如下: <?php $zhan=array("WEB");//声明一个数组当做栈 array_push($zhan,&q

  • PHP SPL标准库之数据结构堆(SplHeap)简单使用实例

    PHP SPL标准库之数据结构堆(SplHeap)简单使用实例

    堆(Heap)就是为了实现优先队列而设计的一种数据结构,它是通过构造二叉堆(二叉树的一种)实现.根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆.二叉堆还常用于排序(堆排序). 如下:最小堆(任意节点的优先级不小于它的子节点) 看看PHP SplHeap的实现: 显然它是一个抽象类,最大堆(SplMaxHeap)和最小堆(SplMinHeap)就是继承它实现的.最大堆和最小堆并没有额外的方法 SplHeap的简单使用如下: class MySimpleHeap extends

  • PHP 各种排序算法实现代码

    复制代码 代码如下: <?php // 功能: PHP实现各种排序算法 // Author: windlike // Datetime: 2007-06-09 // 冒泡排序 function BubbleSort($arr){ $num = count($arr); for($i=1;$i<$num;$i++){ for($j=$num-1;$j>=$i;$j--){ if($arr[$j]<$arr[$j-1]){ $iTemp = $arr[$j-1]; $arr[$j-1]

  • PHP 冒泡排序算法的实现代码

    基本概念 冒泡排序的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面.即首先比较第1 个和第2个数,将小数放前,大数放后.然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后.重复以上过程,仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再大于第2个数),将小数放前,大数放后,一直比较到最小数前的一对相邻数,将小数放前,大数放后,第二趟结束,在倒数第二个数中得到一个新的最小数.如此下去,直至最终完成排序. 由

  • PHP实现的堆排序算法详解

    PHP实现的堆排序算法详解

    本文实例讲述了PHP实现的堆排序算法.分享给大家供大家参考,具体如下: 经验 工作了,面试我工作这家公司时被技术面打击得不行,因为自己的数据结构等基础学得实在太差,虽然原来是想做设计师的说...不过看在PHP写得还凑合的份上能来实习了,但还是决心恶补一下基础. 其实自己之前也确实感觉到了基础的重要性,一些比较深的东西都比较底层,不学好根本没法进行.像我之前用PHP做websocket,就牵扯到数据包.数据帧等概念,搞不清楚,连数据都没法处理,还得后来补.所以我准备重新学一下数据结构,算法,网络等

  • PHP 快速排序算法详解

    PHP 快速排序算法详解

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

随机推荐