<?php namespace iphp\algorithm; /** * Created by PhpStorm. * User: 123 * Date: 14-9-3 * Time: 下午3:53 */ class Sort { /** * 冒泡排序 * 算法,相邻2个元素比较,如果前大于后者,交换位置 * 第一次比较,将最大的元素排在了最后。 * 需要n-1次冒泡 * @param $arr * @return mixed */ public static function bubble($arr) { $num=count($arr); if($num<=1) return $arr; //些标识用于判断如果有一次没有经过交换。那么不需要再进行下一次循环 $flag=false; for($i=0;$i<$num-1;$i++) { for($j=0;$j<$num-1-$i;$j++) { //交换元素 if($arr[$j]>$arr[$j+1]) { $tmp=$arr[$j]; $arr[$j]=$arr[$j+1]; $arr[$j+1]=$tmp; $flag=true; } } if($flag==false) break; } return $arr; } /** * 选择排序 * 第一次,取每1-n个元素之间的最小值,与第0个元素比较,并将最小的放在前面。 * @param $arr * @return mixed */ public static function select($arr) { $num=count($arr); if($num<=1) return $arr; for($i=0;$i<$num-1;$i++) { $minValue=$arr[$i]; $minIndex=$i; for($j=$i+1;$j<$num;$j++) { if($minValue>$arr[$j]) { $minValue=$arr[$j]; $minIndex=$j; } } //交换位置 if($i!=$j) { $tmp=$arr[$i]; $arr[$i]=$minValue; $arr[$minIndex]=$tmp; } } return $arr; } /** * 插入排序 * 最开始将数组的第一个元素当作已经排序的数组。将后面的元素与已排好序的比较,将其插入到已排序中的适当位置。 * @param $arr * @return mixed */ public static function insert($arr) { $num=count($arr); if($num<=1) return $arr; for($i=1;$i<$num;$i++) { $insertValue=$arr[$i]; $insertIndex=$i-1; while($insertIndex>=0 && $insertValue<$arr[$insertIndex]) { $arr[$insertIndex+1]=$arr[$insertIndex]; $insertIndex--; } $arr[$insertIndex+1]=$insertValue; } return $arr; } /** * 快速排序 * @param $arr * @return array */ public static function quick($arr) { $num=count($arr); if($num<=1) return $arr; $middle=$arr[0]; $leftArr=array(); $rightArr=array(); for($i=1;$i<$num;$i++) { if($arr[$i]<=$middle) $leftArr[]=$arr[$i]; else $rightArr[]=$arr[$i]; } $leftArr=self::quick($leftArr); $rightArr=self::quick($rightArr); return array_merge($leftArr,array($middle),$rightArr); } }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。