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] = $arr[$j];
$arr[$j] = $iTemp;
}
}
}
return $arr;
}

// 交换法排序
function ExchangeSort($arr){
$num = count($arr);
for($i=0;$i<$num-1;$i++){
for($j=$i+1;$j<$num;$j++){
if($arr[$j]<$arr[$i]){
$iTemp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $iTemp;
}
}
}
return $arr;
}

// 选择法排序
function SelectSort($arr){
$num = count($arr);
for($i=0;$i<$num-1;$i++){
$iTemp = $arr[$i];
$iPos = $i;
for($j=$i+1;$j<$num;$j++){
if($arr[$j]<$iTemp){
$iTemp = $arr[$j];
$iPos = $j;
}
}
$arr[$iPos] = $arr[$i];
$arr[$i] = $iTemp;
}
return $arr;
}

// 插入法排序
function InsertSort($arr){
$num = count($arr);
for($i=1;$i<$num;$i++){
$iTemp = $arr[$i];
$iPos = $i-1;
while(($iPos>=0) && ($iTemp<$arr[$iPos])){
$arr[$iPos+1] = $arr[$iPos];
$iPos--;
}
$arr[$iPos+1] = $iTemp;
}
return $arr;
}

// 快速排序
function QuickSort($arr){
$num = count($arr);
$l=$r=0;
for($i=1;$i<$num;$i++){
if($arr[$i] < $arr[0]){
$left[] = $arr[$i];
$l++;
}else{
$right[] = $arr[$i];
$r++;
}
}
if($l > 1){
$left = QuickSort($left);
}
$new_arr = $left;
$new_arr[] = $arr[0];
if($r > 1){
$right = QuickSort($right);
}
for($i=0;$i<$r;$i++){
$new_arr[] = $right[$i];
}
return $new_arr;
}

$arr = array(7,1,6,5,2);
$arr_new = QuickSort($arr);
echo "<pre>";
print_r($arr_new);
echo "</pre>";
?>

时间: 2009-08-17

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 快速排序算法详解

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

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

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

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

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

关于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 冒泡排序算法的实现代码

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

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

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排序算法之快速排序(Quick Sort)及其优化算法详解

本文实例讲述了PHP排序算法之快速排序(Quick Sort)及其优化算法.分享给大家供大家参考,具体如下: 基本思想: 快速排序(Quicksort)是对冒泡排序的一种改进.他的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,整个排序过程可以递归进行,以达到整个序列有序的目的. 基本算法步骤: 举个栗子: 假如现在待排序记录是: 6   2   7   3   8   9 第一步.创建变量 $low 指

php数据结构与算法(PHP描述) 查找与二分法查找

复制代码 代码如下: <?php /** * 查找 * **/ // 顺序查找 function normal_search($arrData,$val) { $len = count($arrData); if($len == 0) return -1; for($i = 0;$i < $len; $i++ ) { echo "find No.",$i + 1," value = ",$arrData[$i]," is = ",$v

Java数据结构及算法实例:冒泡排序 Bubble Sort

/** * 冒泡排序估计是每本算法书籍都会提到的排序方法. * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列. * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置, * 即每次把未排好的最大元素冒泡到序列最后端. * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始. * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素. * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置. * 由此可见冒泡排序的复杂

Java数据结构及算法实例:插入排序 Insertion Sort

/** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

Python实现的数据结构与算法之快速排序详解

本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

java数据结构与算法之快速排序详解

本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

Python数据结构与算法(几种排序)小结

Python数据结构与算法(几种排序) 数据结构与算法(Python) 冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 对每一对相邻元素作同样的工作,从

java数据结构与算法之插入排序详解

本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

C#常用数据结构和算法总结

1.数据 数据(Data)是外部世界信息的载体, 是能够被计算机识别,加工,存储的.在现实生活中也就是我们的产品原材料. 计算机中的数据包括数值数据,图片,影音资料等. 2. 数据元素和数据项 数据元素(Data Element)是数据的基本单位,在计算机处理的过程中通常是作为一个整体来作为处理的. 数据项(Data Item):一个数据元素通常由一个或多个数据项组成. 比如数据库表:(Student),它有Id,Name,Sex,Age,Address等字段,而这张表又有多行数据.我们通常将这