<?php
/*
插入排序、选择排序、，冒泡排序，时间复杂度貌似都是 O(N2)，快速排序一般较快
*/
class Sort{
//插入排序
public function insertSort($arr){
$count=count($arr);
if($count<=1)
return $arr;
for($i=1;$i<$count;$i++){
$temp=$arr[$i];
$j=$i-1;
while($j>-1&&$arr[$j]>$temp){
$arr[$j+1]=$arr[$j];
$arr[$j]=$temp;
$j--;
}
}
return $arr;
}
//选择排序
public function selectSort($arr){
$count=count($arr);
if($count<=1)
return $arr;
for($i=0;$i<$count-1;$i++){
$min=$i;
for($j=$i+1;$j<$count;$j++){
if($arr[$j]<$arr[$min])
$min=$j;
if($min!=$i){
$temp=$arr[$i];
$arr[$i]=$arr[$min];
$arr[$min]=$temp;
}
}
}
return $arr;
}
//冒泡排序
public function bubbleSort1($arr){
$count=count($arr);
if($count<=1)
return $arr;
for($i=0;$i<$count;$i++){
for($j=$count-1;$j>$i;$j--){
if($arr[$j]<$arr[$j-1]){
$temp=$arr[$j];
$arr[$j]=$arr[$j-1];
$arr[$j-1]=$temp;
}
}
}
return $arr;
}
public function bubbleSort2($arr){
$count=count($arr);
if($count<=1)
return $arr;
for($i=0;$i<$count-1;$i++){
for($j=0;$j<$count-1-$i;$j++){
if($arr[$j]>$arr[$j+1]){
$temp=$arr[$j];
$arr[$j]=$arr[$j+1];
$arr[$j+1]=$temp;
}
}
}
return $arr;
}
//快速排序
public function quickSort($arr){
$count=count($arr);
if($count<=1)
return $arr;
$key=$arr[0];
$left_arr=array();
$right_arr=array();
for($i=1;$i<$count;$i++){
if($arr[$i]<=$key){
$left_arr[]=$arr[$i];
}else{
$right_arr[]=$arr[$i];
}
}
$left_arr=$this->quickSort($left_arr);//注意递归的时候要加上$this->，因为类的方法是有作用域的
$right_arr=$this->quickSort($right_arr);
return array_merge($left_arr,array($key),$right_arr);
}
}
//测试，测试一定要在class外
$array=array(12,15,9,20,6,31,24);
$sort=new Sort();
$arr=$sort->bubbleSort2($array);
print_r($arr);
?>
| 
转播
