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