PHP实现数据结构中的排序算法

冒泡排序

【基本原理】

相邻两数依次比较,将小数放在前面,大数放在后面。第一趟结束,将最大的数放到了最后。第二趟结束,将最大的数放到了倒数第二。依次一直下去,直至最终完成排序。

冒泡排序,只需要使用两重循环实现,时间复杂度为O(n*n)。

【代码实现】

实现:两两比较,把小的数放在前面

 

<?phpfunction bubble_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		for($i=0;$i < $len-1;$i++)	{		$flag = false;				for($j=0;$j < $len-$i-1;$j++)		{			if($array[$j] > $array[$j+1])			{				$temp=$array[$j];								$array[$j]=$array[$j+1];								$array[$j+1]=$temp;								$flag = true;			}		}		if(! $flag)//本趟排序没有值交换,则提前终止程序  			return $array;	}}//调用实现$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(bubble_sort($array));?>

希尔排序

【基本原理】

         先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1

的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复

上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行

直接插入排序为止。

【代码实现】

实现:与增量间隔的数比较,直到把大的数放到最后

<?php/*** 数据结构中希尔排序PHP实现 ** 时间复杂度为 O(N*(logN)2)*/function shell_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		$d=$len;//随机增量,初始值为数组长度,以不断除2取值		while($d >1)	{		$d=intval($d / 2);//分组间隔,2为n值,n值减少时,移动的趟数和数据增多			$temp=NULL;			$j=0;			for($i=$d;$i < $len;$i+=$d)		{			if($array[$i] < $array[$i-$d])			{				$temp=$array[$i];								$j=$i-$d;								while(($j >=0) && $temp < $array[$j])				{					$array[$j+$d]=$array[$j];										$j = $j - $d;				}								$array[$j+$d]=$temp;			}		}	}	return $array;}$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(shell_sort($array));?>

选择排序

【基本原理】

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

【代码实现】

实现:两次循环,全部比较找出最小元素的key(数组中的索引),判断当前数与最小值key,不相等即交换值

<?php/*** 数据结构中选择排序PHP实现 ** 时间复杂度为 O(n2)*/function select_sort($array){	if(!is_array($array))	{		return false;	}		$len=count($array);		for($i=0;$i < $len;$i++)	{		$k=$i;				for($j=$i+1;$j < $len;$j++)		{			if($array[$k] > $array[$j])			{				$k=$j;			}		}		if($i!=$k){			$temp = $array[$i];        	$array[$i] = $array[$k];        	$array[$k] = $temp;		}	}	return $array;}$array = array(7, 2, 4, 1, 6, 3, 8, 0, 5);print_r(select_sort($array));?>

文章来源:http://meego123.net/?post=126

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » PHP实现数据结构中的排序算法

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡