`
- 浏览:
6821393 次
- 性别:
- 来自:
上海
-
【捷哥浅谈PHP】第二弹---经典算法的运用(冒泡排序和快速排序)
首先说说冒泡排序的思想,那很多同学会问什么是冒泡排序法呢?
下面我来解释下:所谓的冒泡排序法,就是依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
咱们来看个例子:有一个数组array(23,34,12,56,43,98,89),下面我们来使用冒泡排序法来对其元素进行排序.
- <?php
- $arr = Array(23,34,12,56,43,98,89);
- for($i=0;$i<count($arr);$i++){
- for($j=0;$j<count($arr)-1;$j++){
- if($arr[$j]>$arr[$j+1]){
- $tmp = $arr[$j];
- $arr[$j] = $arr[$j+1];
- $arr[$j+1] = $tmp;
- }
- }
- }
- ?>
在上面的例子中,里面的for循环,是将本数组中的所有元素依次两两相比,也就是将数组中的第一个元素和第二个元素相比,第二个元素与第三个元素相比,依此类推,直到数组的倒数第二个元素与最后一个元素相比,如果前面的元素大于后面的元素就让前面的元素与后面的元素位置交换,那我们想,怎么让数组中的两个元素位置交换呢,我们可以使用一个中间的容器变量来解决这个问题,也就是将需要交换的第一个变量的值放入容器变量,然后将需要交换的第二个变量的值赋给第一个变量,再将容器变量中的值赋给第二个变量即可.
为了让大家更深刻的理解,请看下面的模拟图:第一步:声明一个中间容器变量$tmp:第二步:将$arr[$j]的值赋给$tmp
第三步:将$arr[$j+1]赋值给$arr[$j]
第四步:将中间变量的值赋给$arr[$j+1],完成交换依次类推,一直到数组的倒数第二个元素与最后一个元素比较完成.总共比较count($arr)-1次至此,我们数组的第一趟排序也就完成,此时数组中最大的数已经放到了数组的最后.也就是说,内层的for循环已经执行完成.接下来我们需要进行第二趟,第三趟....排序,每排一趟,出一个最大的数放在数组后面,只要排完,总共排count($arr)趟.说到这里,大家是不是明白外层for循环的意思了呢!好,我们思考一个问题,如果数组内的元素两两比较完,每比较一趟排出一个最大数,那我们是不是在下趟比较的时候,不执行和上趟排出来的最大数的比较呢,也就是说,第一趟排序完,98已经被放到了数组的最后,下趟排序就无需再把98拿来比较了,这样会提高效率,节省资源,因此我们可以这样写:<?php
- $arr = Array(23,34,12,56,43,98,89);
- for($i=0;$i<count($arr);$i++){
- for($j=0;$j<count($arr)-$i;$j++){
- if($j==count($arr)-1){
- continue;
- }
- if($arr[$j]>$arr[$j+1]){
- $tmp = $arr[$j];
- $arr[$j] = $arr[$j+1];
- $arr[$j+1] = $tmp;
- }
- }
- }
- ?>
上述代码中,内层循环执行次数变成了count($arr)-$i,也就是说每趟把数组内的所有元素两两比较完之后,下趟再进行此排序时,排序的次数会减一,也就是排除上一趟比较得出的最大的数的比较,这样一来,效率会提升不少,我们可以使用php的内建函数microtime()在执行排序前执行一次,在排序后执行一次,将两次的时间相减,即得出运算时间,通过比较可以得出冒泡排序的第二种排序方法的效率要高于第一种排序方法,但不是很明显,大家下来可以验证下,这里就不多讲了.
下面我们使用快速排序法对以上数组进行排序:<?php
- $arr = Array(23,34,12,56,43,98,89);
- function quick($arr){
- $left = array();
- $right = array();
- if(count($arr)<=1){
- return $arr;
- }
- for($i=1;$i<count($arr);$i++){
- if($arr[0]>$arr[$i]){
- $left[] = $arr[$i];
- }else{
- $right[] = $arr[$i];
- }
- }
- $left = quick($left);
- $right = quick($right);
- return array_merge($left,array($arr[0]),$right);
- }
- ?>
所谓快速排序,就是在$arr数组中任意取一个值作为中间值,然后将这个值与数组内其他所有元素相比较,比这个值小的放到左边,比这个值大的放到这个值的右边, 此时完成一趟排序.以此类推,再将这个值左边的数进行上述排序,同样对右边的数进行上述排序.直到将所有的值都比较完.我们来看上面的代码:首先使用快速排序的理念就需要使用递归,说到递归,就是用函数自己调用自己,逐层深入,最后将拿到的值返回的思想.下面我们来看,首先我们需要自定义一个函数quick(),让此函数自己调用自己.这里中间值我们用$arr[0],这个是随意取的,不是必须的,为了让大家思路清晰,我们先定义两个空数组,就相当于两个杯子,让$arr[0]与数组内所有的值进行比较,比$arr[0]小的值放到第一个杯子中,比$arr[0]大的放到第二个杯子中,在程序中分别为$left和$right,我们判断,如果给定的数组元素只有一个或为空,此数组将被quick函数返回,不再执行下面的内容,接下来我们对数组进行遍历,并用遍历出来的值分别与$arr[0]进行比较,比$arr[0]小的值存入$left数组,比$arr[0]大的的值存入$right数组,此时完成一趟排序,接下来再对$left数组和$right数组进行同样的操作,也就是调用函数自己,将$left数组和$right数组传入,直到$left数组或$right数组的数组元素为一个时,不再调用自己,直接返回,最后将左边的数组,$arr[0],$right数组合并,即可得到最终的排序结果.修正:纠正效率方面的问题,在测试效率的时候,发生一个错误,导致效率测试不准确,经各位同学提醒,又一再测试,最终发现对此数组排序时运用快速排序的运算效率与冒泡排序的第二种相差不多,但是冒泡的第一种还是要比第二种明显的高一些,这个测试结果只能作为参考,要精确地算出每种算法的效率,需要对算法内部进行排序次数的统计.再次感谢各位同学的关注,以及对于此问题的纠正,这是一个开放的平台,请大家畅所欲言,多多交流,共同进步...
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
C# 常用经典算法,选择排序 冒泡排序 快速排序 插入排序 希尔排序
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
1.冒泡排序的原理:每次都从第一个元素开始(索引0),向后两两比较,只要后面的比前面的大,就交换(从大到小) 2.通过画图分析,5个数字排4趟,n数字排n-1趟,而外层的for循环代表的是循环的趟数,所以外层循环的结束条件是...
1冒泡排序 2改进的冒泡排序,在一次冒泡的过程中,如果没有发生交换,则已经有序 3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
算法-数据结构和算法-9-冒泡排序.rar
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
用C++语言实现的几个常见算法,里面有注解,方便大家理解,简单易学,都可以正常编译运行。
试通过随机数据比较快速排序、起泡排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字...
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
C++实现冒泡排序,多层次,快速实现排序算法