PHP快速排序quicksort实例详解
本文实例讲述了PHP快速排序quicksort。分享给大家供大家参考，具体如下：
quicksort
在快速排序算法中，使用了分治策略。首先把序列分成两个子序列，递归地对子序列进行排序，直到整个序列排序结束。（即一分为二的思想）
步骤如下：
在序列中选择一个关键元素做为轴；
对序列进行重新排序，将比轴小的元素移到轴的前边，比轴大的元素移动到轴的后面。在进行划分之后，轴便在它最终的位置上；
递归地对两个子序列进行重新排序：含有较小元素的子序列和含有较大元素的子序列。
比如序列$arr:
5 3 0 11 44 7 23 2 将第一个元素$arr[0] = 5 作为轴 设置标志位 low … top代表首尾
2 3 0 11 44 7 23 2 从相反方向（右）开始比较：2<5 将第一个位置替换为2，low++
2 3 0 11 44 7 23 11 从相反方向（左）开始比较直到：5<11 将最后一个位置替换为11,top–
重复以上步骤直到 low == top 把该位置替换为轴元素即5
2 3 0 5 44 7 23 11
这样就可分为两部分2 3 0 与 44 23 11
这样就可以得出递归继续开始步骤
算法实现：
class quick_sort{
function quicksort(&$arr,$low,$top){
if($low < $top){
$pivotpos = $this->partition($arr,$low,$top);
$this->quicksort($arr,$low,$pivotpos-1);
$this->quicksort($arr,$pivotpos+1,$top);
}
}
function partition(&$arr, $low ,$top){
if($low == $top){
return;
}
// 设置初始数值
$com = $arr[$low];
while($low!=$top){
// 将比初始数值小的替换到左边
while($top&&$top!=$low){
if($com > $arr[$top]){
$arr[$low++] = $arr[$top];
break;
}else{
$top--;
}
}
// 将比初始数值大的替换到右边
while($low&&$low!=$top){
if($com < $arr[$low]){
$arr[$top--] = $arr[$low];
break;
}else{
$low++;
}
}
}
$arr[$low] = $com;
return $low;
}
}
更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《php面向对象程序设计入门教程》、《PHP数学运算技巧总结》、《PHP数组(Array)操作技巧大全》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php正则表达式用法总结》、及《php常见数据库操作技巧汇总》
希望本文所述对大家PHP程序设计有所帮助。
相关推荐
-
php类的自动加载操作实例详解
本文实例讲述了php类的自动加载操作.分享给大家供大家参考,具体如下: 类的自动加载 在外面的页面中,并不需要去引入类文件,但程序会在需要一个类的时候自动去"动态加载"该类. ① 创建一个对象的时候new ② 直接使用一个类名(操作静态属性与方法) 使用__autoload魔术函数 当出现两种情况时候,就会调用该函数,该函数需要我们预先定义,在其中写好加载类文件的通用语句 function __autoload($name){ require './lib/'.$name.'.clas
-
PHP 闭包详解及实例代码
闭包和匿名函数在PHP5.3.0中引入的. 闭包是指:创建时封装周围状态的函数.即使闭包所处的环境不存在了,闭包中封装的状态依然存在. 理论上,闭包和匿名函数是不同的概念.但是PHP将其视作相同概念. 实际上,闭包和匿名函数是伪装成函数的对象.他们是Closure类的实例. 闭包和字符串.整数一样,是一等值类型. 创建闭包 <?php $clousre = function ($name) { return 'Hello ' . $name; }; echo $closure('nesfo');
-
PHP二分查找算法示例【递归与非递归方法】
本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9
-
PHP类相关知识点实例总结
本文实例总结了PHP类相关知识点.分享给大家供大家参考,具体如下: 最终类与最终方法 如果父类中的方法被声明为 final,则子类无法覆盖该方法.如果一个类被声明为 final,则不能被继承. final class a{} class a{ final public function A(){} } 抽象类与抽象方法 abstract class a { public abstract function func(); } class A extends a{ public function
-
PHP的Json中文处理解决方案
本文讲述了PHP的Json中文处理解决方案.分享给大家供大家参考,具体如下: Json是现在被广泛使用的用于传递字符串的格式,相比xml更显得简单易懂以及更方便操作,php下就俩个函数,json_encode() AND json_deconde().不过json对中文的支持并不是很好,如果使用json_encode()处理如数组,数组中若存在中文,则会作空白处理. 解决中文的一种方法就是先将中文转换为另一种编码格式,然后再使用json_encode(),最后再用解码把json串进行解码.还有一
-
分享一个漂亮的php验证码类
本文实例为大家分享了一个漂亮的php验证码类,供大家参考,具体内容如下 //验证码类 class ValidateCode { private $charset = 'abcdefghkmnprstuvwxyzABCDEFGHKMNPRSTUVWXYZ23456789';//随机因子 private $code;//验证码 private $codelen = 4;//验证码长度 private $width = 130;//宽度 private $height = 50;//高度 privat
-
PHP遍历目录函数opendir()、readdir()、closedir()、rewinddir()总结
在进行PHP编程时,需要对服务器某个目录下面的文件进行浏览,通常成为遍历目录.取得一个目录下的文件和子目录,就需要用到opendir()函数.readdir()函数.closedir()函数和rewinddir()函数. ①函数opendir() 函数opendir()用于打开指定目录,接受一个目录的路径及目录名作为参数,函数返回值为可供其他目录函数使用的目录句柄(资源类型).如果该目录不存在或者没有访问权限,则返回FALSE. ②函数readdir() 函数readdir()用于读取指定目录,
-
PHP实现QQ快速登录的方法
前言: PHP实现QQ快速登录,罗列了三种方法 方法一:面向过程,回调地址和首次触发登录写到了一个方法页面[因为有了if做判断], 方法二,三:面向对象 1.先调用登录方法,向腾讯发送请求, 2.腾讯携带本网站唯一对应参数OPENID,ACCESSTOKEN,返回到对应回调页面, 3.回调页面接受到腾讯的参数后,通过这个两个参数,再发出对应的请求,如查询用户的数据. 4.腾讯做出对应的操作,如返回这个用户的数据给你 即使你没看懂,也没关系,按照我下面的流程来,保证你可以实现. 前期准备: 使用人
-
php opendir()列出目录下所有文件的实例代码
php opendir()函数用于打开目录,通常与readdir()和closedir()函数一起用来读取目录下所有文件(即遍历目录),本文章向大家介绍php使用opendir()函数列出目录下所有文件的实例. 实例一: 使用opendir()列出目录下所有文件 <?php $dr = @opendir('/tmp/'); if(!$dr) { echo "Error opening the /tmp/ directory!<BR>"; exit; } while((
-
PHP快速排序quicksort实例详解
本文实例讲述了PHP快速排序quicksort.分享给大家供大家参考,具体如下: quicksort 在快速排序算法中,使用了分治策略.首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束.(即一分为二的思想) 步骤如下: 在序列中选择一个关键元素做为轴: 对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面.在进行划分之后,轴便在它最终的位置上: 递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列. 比如序列$arr: 5 3 0
-
C语言数据结构 快速排序实例详解
C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart
-
JavaScript算法系列之快速排序（Quicksort）算法实例详解
"快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,
-
python 二分查找和快速排序实例详解
思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e
-
Python字符串处理实例详解
Python字符串处理实例详解 一.拆分含有多种分隔符的字符串 1.如何拆分含有多种分隔符的字符串 问题: 我们要把某个字符串依据分隔符号拆分不同的字段,该字符串包含多种不同的分隔符,例如: s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz" 其中;,|,\t 都是分隔符号,如何处理? 方法一: 连续使用str.split()方法,每次处理一种分隔符号 s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz&q
-
数据结构之归并排序的实例详解
归并排序 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列:即先使每个子序 列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表:将这些有序序列 再次归并,得到n/4个长度为4的有序序列:如此反复进行下去,最后得到一个长度为n的有序序列.所以呢,我们总结一下归并排序 其实就只有两步:
-
C语言中qsort函数的用法实例详解
C语言中qsort函数的用法实例详解 快速排序是一种用的最多的排序算法,在C语言的标准库中也有快速排序的函数,下面说一下详细用法. qsort函数包含在<stdlib.h>中 qsort函数声明如下: void qsort(void * base,size_t nmemb,size_t size ,int(*compar)(const void *,const void *)); 参数说明: base,要排序的数组 nmemb,数组中元素的数目 size,每个数组元素占用的内存空间,可使用si
-
PHP排序算法之归并排序(Merging Sort)实例详解
本文实例讲述了PHP排序算法之归并排序(Merging Sort).分享给大家供大家参考,具体如下: 基本思想: 归并排序:就是利用归并(合并)的思想实现的排序方法.它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列:再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序. 一.归并
-
PHP排序算法之基数排序(Radix Sort)实例详解
本文实例讲述了PHP排序算法之基数排序(Radix Sort).分享给大家供大家参考,具体如下: 基数排序在<大话数据结构>中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来. 基本思想: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶&quo
-
JS中数据结构与算法---排序算法(Sort Algorithm)实例详解
排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1) 内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,