PHP各种排序算法比较

标准

稻子:

冒泡排序

基本思想:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。

<?php //冒泡排序 $arr=array(1,3,5,56,132,-4); $temp=0; //外层循环 for($i=0;$i<count($arr)-1;$i++){ //内层循环 for($j=0;$j<count($arr)-1-$i;$j++){ if($arr[$j]>$arr[$j+1]){ //只要后边的比前一个大,就交换 $temp=$arr[$j+1]; $arr[$j+1]=$arr[$j]; $arr[$j]=$temp; } } } print_r($arr); ?>

快速排序

基本思想:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

<?php //选择排序 $arr=array(1,23,4,2,56); $temp=0; //循环找最小值 for($i=1;$i<count($arr)-1;$i++){ //初始化$i值最小 $minIndex=$i; $minVal=$arr[$i]; for($j=$i+1;$j<count($arr);$j++){ //如果找到比$i的值小的,则记录 if($minVal>$arr[$j]){ $minVal=$arr[$j]; $minIndex=$j; } } //交换 $temp=$arr[$i]; $arr[$i]=$minVal; $arr[$minIndex]=$temp; } print_r($arr); ?>

插入排序

基本思想:假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

<?php //选择排序 $arr=array(1,23,4,2,56); for($i=1;$i<count($arr);$i++) { $insertval=$arr[$i]; $insertindex=$i-1; //寻找插入点 while($insertindex>=0&&$insertval<$arr[$insertindex]) { //往后移数字 $arr[$insertindex+1]=$arr[$insertindex]; $insertindex--; } //插入值 $arr[$insertindex+1]=$insertval; } print_r($arr); ?>

快速排序

基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

<?php //选择排序 $arr=array(1,23,4,2,56); function quick_sort_swap(&$array, $start, $end) { if($end <= $start) return; $key = $array[$start]; $left = $start; $right = $end; while($left < $right) { while($left < $right && $array[$right] > $key) $right--; $array[$left] = $array[$right]; while($left < $right && $array[$left] < $key) $left++; $array[$right] = $array[$left]; } $array[$right] = $key; quick_sort_swap(&$array, $start, $right - 1); quick_sort_swap(&$array, $right+1, $end); } quick_sort_swap($arr,0,count($arr)-1); print_r($arr); ?>

写在最后:

冒泡排序效率最低,快速排序效率最高;

快速排序效率高的同时利用了递归,在排序的瞬间会内存暴涨,所以快是有代价的!

发表评论