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次。

(0)

相关推荐

  • 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 二维数组快速排序算法的实现代码

    php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递归. 实例代码: <?php class Bubble { private function __construct() { } private static function sortt($data) { if (count ( $data ) <= 1) { return $data; } $tem = $data [0]['sco

  • PHP快速排序quicksort实例详解

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

  • PHP排序算法之快速排序(Quick Sort)及其优化算法详解

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

  • PHP快速排序算法实例分析

    本文实例讲述了PHP快速排序算法.分享给大家供大家参考,具体如下: 快速排序:在无序的数组$data中,选择任意一个值作为对比值,定义i为头部检索索引,j为尾部检索索引, 算法步骤: (1)初始化对比值$value=$data[0],$i=1,$j=count($data)-1 (2)首先从尾部开始检索,判断$data[$j]是否小于$value,若不小于则$j--,继续检索,直到找到比$value小的坐标 (3)这时开始头部检索,判断$data[$i]是否大于$value,若不大于则$i++,

  • PHP递归实现快速排序的方法示例

    本文实例讲述了PHP递归实现快速排序的方法.分享给大家供大家参考,具体如下: 首先我们要理解一下快速排序的原理:找到当前数组中的任意一个元素(一般选择第一个元素),作为标准,新建两个空数组,遍历整个数组元素,如果遍历到的元素比当前的元素要小,那么就放到左边的数组,否则放到右面的数组,然后再对新数组进行同样的操作. 不难发现,这里符合递归的原理,所以我们可以用递归来实现. 使用递归,则需要找到递归点和递归出口: 递归点:如果数组的元素大于1,就需要再进行分解,所以我们的递归点就是新构造的数组元素个

  • PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

    本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

  • PHP快速排序算法实现的原理及代码详解

    算法原理 下列动图来自五分钟学算法,演示了快速排序算法的原理和步骤. 步骤: 从数组中选个基准值 将数组中大于基准值的放同一边.小于基准值的放另一边,基准值位于中间位置 递归的对分列两边的数组再排序 代码实现 function quickSort($arr) { $len = count($arr); if ($len <= 1) { return $arr; } $v = $arr[0]; $low = $up = array(); for ($i = 1; $i < $len; ++$i)

  • C语言中使用快速排序算法对元素排序的实例详解

    调用C语言的快速排序算法qsort(); #include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 100 //从小到大排序 int comp1(const void *x,const void *y) { return *(int *)x - *(int *)y; } //从大到小排序 int comp2(const void *x,const void *y) { return *(in

  • SpringBoot Application注解原理及代码详解

    1.SpringBoot 启动main() @SpringBootApplication public class TomcatdebugApplication { public static void main(String[] args) { SpringApplication.run(TomcatdebugApplication.class, args); } } 1.1 @SpringBootApplication 注解,其实主要是@ComponentScan,@EnableAutoCo

  • C语言冒泡排序算法代码详解

    今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在一个周期中,微观上依次进行两两元素的比较,小的元素就被放在前面,大的元素放在后面,以此来进行N-1个周期,来完成冒泡排序. 上文中的一个周期,即外循环,依次进行比较,即内循环. 文字看着很迷糊?没事儿,上图 如图所示,两两元素依次进行比较,小的元素往前移动,大的元素往后移动,直至元素顺序是升序的形式,即移动了 元素-

  • Java中Prime算法的原理与实现详解

    目录 Prim算法介绍 1.点睛 2.算法介绍 3. 算法步骤 4.图解 Prime 算法实现 1.构建后的图 2.代码 3.测试 Prim算法介绍 1.点睛 在生成树的过程中,把已经在生成树中的节点看作一个集合,把剩下的节点看作另外一个集合,从连接两个集合的边中选择一条权值最小的边即可. 2.算法介绍 首先任选一个节点,例如节点1,把它放在集合 U 中,U={1},那么剩下的节点为 V-U={2,3,4,5,6,7},集合 V 是图的所有节点集合. 现在只需要看看连接两个集合(U 和 V-U)

  • 基数排序算法的原理与实现详解(Java/Go/Python/JS/C)

    目录 说明 实现过程 示意图 性能分析 代码 Java Python Go JS TS C C++ 链接 说明 基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数.基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的 基数排序的方式可以采用LSD(Least significant di

  • Matlab中图像数字水印算法的原理与实现详解

    目录 一.背景意义 二.基本原理 三.算法介绍 3.1 数字水印嵌入 3.2 数字水印提取 四.程序实现 一.背景意义 数字水印技术作为信息隐藏技术的一个重要分支,是将信息(水印)隐藏于数字图像.视频.音频及文本文档等数字媒体中,从而实现隐秘传输.存储.标注.身份识别.版权保护和防篡改等目的. 随着 1996 年第一届信息隐藏国际学术研讨会的召开,数字水印技术的研究得到了迅速的发展,不少政府机构和研究部门加大了对其的研究力度,其中包括美国财政部.美国版权工作组.美国洛斯阿莫斯国家实验室.美国海陆

  • Java编程实现快速排序及优化代码详解

    普通快速排序 找一个基准值base,然后一趟排序后让base左边的数都小于base,base右边的数都大于等于base.再分为两个子数组的排序.如此递归下去. public class QuickSort { public static <T extends Comparable<? super T>> void sort(T[] arr) { sort(arr, 0, arr.length - 1); } public static <T extends Comparabl

  • 机器学习经典算法-logistic回归代码详解

    一.算法简要 我们希望有这么一种函数:接受输入然后预测出类别,这样用于分类.这里,用到了数学中的sigmoid函数,sigmoid函数的具体表达式和函数图象如下: 可以较为清楚的看到,当输入的x小于0时,函数值<0.5,将分类预测为0:当输入的x大于0时,函数值>0.5,将分类预测为1. 1.1 预测函数的表示 1.2参数的求解 二.代码实现 函数sigmoid计算相应的函数值:gradAscent实现的batch-梯度上升,意思就是在每次迭代中所有数据集都考虑到了:而stoGradAscen

  • Java版超大整数阶乘算法代码详解-10,0000级

    当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数

随机推荐