• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

常见排序算法 php示例代码

实用代码 开心洋葱 2364次浏览 0个评论

常见排序算法 php示例代码

 

常见排序算法
 
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

 

<?php


//常见排序算法

//快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

//Shell排序
//鸡尾酒排序
//堆排序
//冒泡排序算法
/*
 * 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
 * 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
 * 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
 */
function bubbleSort($numbers)
{
	$cnt=count($numbers);
	for($i=0;$i<$cnt-1;$i++){//循环比较
		for($j=$i+1;$j<$cnt;$j++){
			echo $i.':'.$numbers[$i].'_'.$j.':'.$numbers[$j]."<br/>\r\n";
			echo '----------------------<br/>';
			var_dump($numbers);
			echo '----------------------<br/>';
				
			if($numbers[$i]>$numbers[$j]){//执行交换
				$temp=$numbers[$i];
				$numbers[$i]=$numbers[$j];
				$numbers[$j]=$temp;
			}
		}
		echo '==================<br/>';
		var_dump($numbers);
	}
	return$numbers;
}

//直接插入排序算法
/*
 * 	每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
	第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,
	把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
 */
function charupaixu($numbers){
	
	$count = count($numbers);
	
	for($i=2;$i<$count;$i++){
			
		if($numbers[$i]<$numbers[$i-1]){
			$temp = $numbers[$i];
			for($j=$i-1;$j>=0&&$numbers[$j]>$temp;$j--)
				$numbers[$j+1]=$numbers[$j];
			$numbers[$j+1]=$temp;
			
		}
	}
	
	return $numbers;
}

//直接选择排序算法
/*
 * 直接选择排序(Straight Select Sorting) 也是一种简单的排序方法,它的基本思想是:
 * 第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,
 * 第二次从R[1]~R[n-1]中选取最小值,与R[1]交换,....,
 * 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,
 * 第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,
 * 总共通过n-1次,得到一个按排序码从小到大排列的有序序列·
 * 
 * 
 * 	例如:给定n=8,数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下所示
	由于百科不方便画出关联箭头 所以用 n -- n 表示 :
	初始状态 [ 8 3 2 1 7 4 6 5 ] 8 -- 1
	第一次 [ 1 3 2 8 7 4 6 5 ] 3 -- 2
	第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3
	第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4
	第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5
	第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6
	第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7
	第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成
 */
function selectsort($numbers){
	$count = count($numbers);
	for($i=0;$i<$count-1;$i++){
		$m=$i;
		for($j=$i+1;$j<$count;$j++){
			if($numbers[$j]<$numbers[$m]) $m=$j;
		}
		
		if($m!=$i){
			$t = $numbers[$i];
			$numbers[$i]=$numbers[$m];
			$numbers[$m]=$t;
		}
		
		var_dump($numbers);
	}
	return  $numbers;
}


//快速排序算法
/*
 * 设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,
 * 然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
 * 值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
 */
function quicksort($numbers){
	$count  = count($numbers);
	if($count>1){
			$k=$numbers[0];
			$x = array();
			$y = array();
			for($i=1;$i<$count;$i++){
				if($numbers[$i]<=$k){
					$x[]=$numbers[$i];
				}elseif($numbers[$i]>$k){
					$y[]=$numbers[$i];
				}
			}	
			$x = quicksort($x);
			$y = quicksort($y);
			return array_merge($x,array($k),$y);
	}else{
		return $numbers;
	}
}


//归并排序算法

/* 
	            归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。
		将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
		例如有两个有序表:(7,10,13,15)和(4,8,19,20),归并后得到的有序表为:(4,7,8,10,13,15,19,20)。
		归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;
		否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

  		归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。
		如 设有数列{6,202,100,301,38,8,1}
		初始状态:6,202,100,301,38,8,1
		第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
		第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
		第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
		总的比较次数为:3+4+4=11,;
		逆序数为14;
 * 
 */

//merge函数将指定的两个有序数组(arr1arr2,)合并并且排序
//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过的数据
function al_merge($arrA,$arrB){
	$arrC = array();
	while(count($arrA)&&count($arrB)){
		//这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
		//不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
		$arrC[]=$arrA['0']<$arrB['0']?array_shift($arrA):array_shift($arrB);
	}
	
	return array_merge($arrC,$arrA,$arrB);
}

//归并排序主程序
function mergesort($numbers){
	$count = count($numbers);
	if($count<=1) return $numbers;//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
	$mid = intval($count/2);//取数组中间
	$left_arr = array_slice($numbers,0,$mid);//拆分数组0-mid这部分给左边left_arr
	$right_arr = array_slice($numbers,$mid);//拆分数组mid-末尾这部分给右边right_arr
	$left_arr = al_merge_sort($left_arr);//左边拆分完后开始递归合并往上走
	$right_arr = al_merge_sort($right_arr);//右边拆分完毕开始递归往上走
	$arr = al_merge($left_arr,$right_arr);//合并两个数组,继续递归
	return $arr;	
}


$num=array(20,40,15,80,30,70,90,10,50,0);
//var_dump(bubbleSort($num));
//var_dump(charupaixu($num));
//var_dump(selectsort($num));
//var_dump(quicksort($num));
?>

 


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明常见排序算法 php示例代码
喜欢 (0)

您必须 登录 才能发表评论!

加载中……