首页 php教程 php手册 php实现快速排序的三种方法分享

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

Jun 06, 2016 pm 08:24 PM
分享 实现 快速 排序 方法

这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下

写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法。三组算法实现和比较如下:

方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))

复制代码 代码如下:


function quick_sort($array) {
 if(count($array)  $key = $array[0];
 $rightArray = array();
 $leftArray = array();
 for($i = 1; $i            if($array[$i] >= $key) {
  $rightArray[] = $array[$i];
    } else {
  $leftArray[] = $array[$i];
    }
 }
 $leftArray = quick_sort($leftArray);
 $rightArray = quick_sort($rightArray);
 return array_merge($leftArray, array($key), $rightArray);
}


方法二:该算法来自算法导论,叫作Nico Lomuto方法(感兴趣goole上有详细说明)使用最经典的单方向一次遍历找到中值。
但这种算法在最坏情况下(例如值相同的数组,需要n-1次划分,每一次划分需要O(n) 时间去掉一个元素)最坏情况下为O(n*n)

复制代码 代码如下:


function quick_sort(&$array, $start, $end) {
    if ($start >= $end) return;
    $mid = $start;
    for ($i = $start + 1; $i  if ($array[$i]      $mid++;
     $tmp = $array[$i];
     $array[$i] = $array[$mid];
     $array[$mid] = $tmp;
 }
    }
    $tmp = $array[$start];
    $array[$start] = $array[$mid];
    $array[$mid] = $tmp;
    quick_sort($array, $start, $mid - 1);
    quick_sort($array, $mid + 1, $end);
}

方法三:该方法基本上是教科书式的常见写法,首先从左向右遍历小于中间元素的跳过,同时从右向左遍历遇到大的元素跳过,然后

如果没有交叉着交换两边值,,继续循环,直到找到中间点。注意该方法在处理相同元素的时候,仍旧交换,这样在最坏情况下也有O(nlogn)

效率。但下面的函数中,如果将$array[$right] > $key 改成 $array[$right] >=$key 或将 $array[$left]

情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销。该题还有另外两个考点,针对死记硬背的同学:

1:中间的两个while可否互换。当然不能互换,因为对于快盘需要一个额外的空间保存初始的左值,这样左右互换的时候,先用右边覆盖已经保存

为中值的左值,否则会出现问题。见这句$array[$left] = $array[$right];

2:$array[$right] = $key; 该语句含义可否省略。该句不能省略,大家可以考虑一个极端情况比如两个值的排序(5,2),逐步看下就明白了。

复制代码 代码如下:


function quick_sort_swap(&$array, $start, $end) {
 if($end  $key = $array[$start];
 $left = $start;
 $right = $end;
 while($left   while($left $key)
   $right--;
  $array[$left] = $array[$right];
  while($left    $left++;
  $array[$right] = $array[$left];
 }
 $array[$right] = $key;
 quick_sort_swap(&$array, $start, $right - 1);
 quick_sort_swap(&$array, $right+1, $end);
}

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

怎么在番茄免费小说app中写小说 分享番茄小说写小说方法教程 怎么在番茄免费小说app中写小说 分享番茄小说写小说方法教程 Mar 28, 2024 pm 12:50 PM

  番茄小说是一款非常热门的小说阅读软件,我们在番茄小说中经常会有新的小说和漫画可以去阅读,每一本小说和漫画都很有意思,很多小伙伴也想着要去写小说来赚取赚取零花钱,在把自己想要写的小说内容编辑成文字,那么我们要怎么样在这里面去写小说呢?小伙伴们都不知道,那就让我们一起到本站本站中花点时间来看写小说的方法介绍吧。分享番茄小说写小说方法教程  1、首先在手机上打开番茄免费小说app,点击个人中心——作家中心  2、跳转到番茄作家助手页面——点击创建新书在小说的结

微信删除的人如何找回(简单教程告诉你如何恢复被删除的联系人) 微信删除的人如何找回(简单教程告诉你如何恢复被删除的联系人) May 01, 2024 pm 12:01 PM

而后悔莫及、人们常常会因为一些原因不小心将某些联系人删除、微信作为一款广泛使用的社交软件。帮助用户解决这一问题,本文将介绍如何通过简单的方法找回被删除的联系人。1.了解微信联系人删除机制这为我们找回被删除的联系人提供了可能性、微信中的联系人删除机制是将其从通讯录中移除,但并未完全删除。2.使用微信内置“通讯录恢复”功能微信提供了“通讯录恢复”节省时间和精力,用户可以通过该功能快速找回之前被删除的联系人,功能。3.进入微信设置页面点击右下角,打开微信应用“我”再点击右上角设置图标、进入设置页面,,

华为手机如何实现双微信登录? 华为手机如何实现双微信登录? Mar 24, 2024 am 11:27 AM

华为手机如何实现双微信登录?随着社交媒体的兴起,微信已经成为人们日常生活中不可或缺的沟通工具之一。然而,许多人可能会遇到一个问题:在同一部手机上同时登录多个微信账号。对于华为手机用户来说,实现双微信登录并不困难,本文将介绍华为手机如何实现双微信登录的方法。首先,华为手机自带的EMUI系统提供了一个很便利的功能——应用双开。通过应用双开功能,用户可以在手机上同

网易云音乐怎么分享到微信朋友圈_网易云音乐分享到微信朋友圈教程 网易云音乐怎么分享到微信朋友圈_网易云音乐分享到微信朋友圈教程 Mar 25, 2024 am 11:41 AM

1、首先我们进入到网易云音乐中,然后在软件首页界面中,点击进入到歌曲的播放界面中。2、然后在歌曲播放界面中,找到右上方的分享功能按钮,如下图红框所示位置,点击选择分享的渠道;在分享渠道中,点击底部的“分享至”选项,然后选择第一个“微信朋友圈”,即可将内容分享至微信朋友圈。

手机版龙蛋孵化方法大揭秘(一步一步教你如何成功孵化手机版龙蛋) 手机版龙蛋孵化方法大揭秘(一步一步教你如何成功孵化手机版龙蛋) May 04, 2024 pm 06:01 PM

手机游戏成为了人们生活中不可或缺的一部分,随着科技的发展。它以其可爱的龙蛋形象和有趣的孵化过程吸引了众多玩家的关注,而其中一款备受瞩目的游戏就是手机版龙蛋。帮助玩家们在游戏中更好地培养和成长自己的小龙,本文将向大家介绍手机版龙蛋的孵化方法。1.选择合适的龙蛋种类玩家需要仔细选择自己喜欢并且适合自己的龙蛋种类,根据游戏中提供的不同种类的龙蛋属性和能力。2.提升孵化机的等级玩家需要通过完成任务和收集道具来提升孵化机的等级,孵化机的等级决定了孵化速度和孵化成功率。3.收集孵化所需的资源玩家需要在游戏中

手机字体大小设置方法(轻松调整手机字体大小) 手机字体大小设置方法(轻松调整手机字体大小) May 07, 2024 pm 03:34 PM

字体大小的设置成为了一项重要的个性化需求,随着手机成为人们日常生活的重要工具。以满足不同用户的需求、本文将介绍如何通过简单的操作,提升手机使用体验,调整手机字体大小。为什么需要调整手机字体大小-调整字体大小可以使文字更清晰易读-适合不同年龄段用户的阅读需求-方便视力不佳的用户使用手机系统自带字体大小设置功能-如何进入系统设置界面-在设置界面中找到并进入"显示"选项-找到"字体大小"选项并进行调整第三方应用调整字体大小-下载并安装支持字体大小调整的应用程序-打开应用程序并进入相关设置界面-根据个人

百度网盘怎么分享文件给好友 百度网盘怎么分享文件给好友 Mar 25, 2024 pm 06:52 PM

近期,百度网盘安卓客户端迎来了全新的8.0.0版本,这一版本不仅带来了众多变化,还增添了诸多实用功能。其中,最为引人注目的便是文件夹共享功能的增强。现在,用户可以轻松邀请好友加入,共同分享工作和生活中的重要文件,实现更加便捷的协作与共享。那么究竟该如何分享给好友自己需要分享的文件呢,下文中本站小编就将为大家带来详细内容介绍,希望能帮助到大家!1)打开百度云APP,首先点击在首页中选择相关的文件夹,然后再点击界面右上角的【...】图标;(如下图)2)随后点击“共享成员”一栏中的【+】,最后在勾选所

Go语言方法与函数的区别及应用场景解析 Go语言方法与函数的区别及应用场景解析 Apr 04, 2024 am 09:24 AM

Go语言方法与函数的区别在于与结构体的关联性:方法与结构体关联,用于操作结构体数据或方法;函数独立于类型,用于执行通用操作。

See all articles