冒泡、快排、直插三种排序的比较

2017-1-11 dingshangchao php开发

<?php
header("Content-Type:text/html;charset=utf-8");
class Test{
	//冒泡排序为从小到大
	public function bubbleSort($arr){
		if(!is_array($arr)) return false;
		if(count($arr) <= 1) return $arr;
		for($i = 0;$i < count($arr);$i++){
			$mark = 0;
			for($j = 0;$j < count($arr) - $i-1;$j++){
				if($arr[$j] > $arr[$j+1]){
					$arr[$j] = $arr[$j] + $arr[$j+1];
					$arr[$j+1] = $arr[$j] - $arr[$j+1];
					$arr[$j] = $arr[$j] - $arr[$j+1];
					$mark = 1;
				}
			}
			if($mark == 0) break;
		}
		return $arr;
	}
	//快速排序为从小到大
	public function quickSort($arr){
		if(!is_array($arr)) return false;
		if(count($arr) <= 1) return $arr;
		$left = $right = array();
		for($i=1;$i<count($arr);$i++){
			if($arr[$i] < $arr[0]){
				$left[] = $arr[$i];
			}else{
				$right[] = $arr[$i];
			}
		}
		$arr = array_merge($left,array($arr[0]),$right);
		if($left) return $this->quickSort($arr);	
		return $arr;
	}
	//直接插入排序为从小到大
	public function insertSort($arr){
		if(!is_array($arr)) return false;
		if(count($arr) <= 1) return $arr;
		$arr1[] = $arr[0];
		for($i = 1 ; $i < count($arr) ; $i++){
			for($j = count($arr1) - 1 ; $j >= 0 ; $j--){
				if($arr1[$j] < $arr[$i]) break;				
				$arr1[$j+1] = $arr1[$j];
			}
			$arr1[$j+1] = $arr[$i];
		}
		return $arr1;
	}
	//网上的插入排序
	function insertSort1($arr) {
	    $len=count($arr); 
	    for($i=1; $i<$len; $i++) {
	        $tmp = $arr[$i];
	        //内层循环控制，比较并插入
	        for($j=$i-1;$j>=0;$j--) {
	            if($tmp < $arr[$j]) {
	                //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
	                $arr[$j+1] = $arr[$j];
	                $arr[$j] = $tmp;
	            } else {
	                //如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
	                break;
	            }
	        }
	    }
	    return $arr;
	}
}

$test  = new Test();

$arr = array();
for($i = 0;$i<2000;$i++){
	$arr[$i] = rand(0,100000);
}

$time1 = microtime(true);
$test->bubbleSort($arr);
$time2 = microtime(true);
echo '耗时'.($time2*1000-$time1*1000).'毫秒';
echo '<br />';
$time1 = microtime(true);
$test->quickSort($arr);
$time2 = microtime(true);
echo '耗时'.($time2*1000-$time1*1000).'毫秒';
echo '<br />';
$time1 = microtime(true);
$test->insertSort($arr);
$time2 = microtime(true);
echo '耗时'.($time2*1000-$time1*1000).'毫秒';
echo '<br />';
$time1 = microtime(true);
$test->insertSort1($arr);
$time2 = microtime(true);
echo '耗时'.($time2*1000-$time1*1000).'毫秒';
echo '<br />';
?>

运行结果：

耗时5249.3747558594毫秒
耗时50.65185546875毫秒
耗时327.828125毫秒
耗时408.43701171875毫秒

分享到： QQ空间新浪微博腾讯微博微信更多

« 阿里云短信服务phpSDK使用方法 | js拖拽排序»

冒泡、快排、直插三种排序的比较

日历

存档

最新评论

链接

搜索