常见排序算法 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));
?>