/*
* php 四种排序算法 的时间与内置的sort 排序比较
* 3000 个元素,四种算法的排序所用的时间比较
* 冒泡排序 857.98192024231 ms
* 选择排序 903.74493598938 ms
* 插入排序 296.8270778656 ms
* 快速排序 15.607833862305 ms
* sort 排序 0 .95200538635254 ms
* 归并排序 14.61386680603 ms
* */
/*
* @param 冒泡排序
* 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
* 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
* */
php">function BubbleSort ($arr ) {
$len = count($arr );
for ($i = 1 ; $i < $len ; $i ++) {
$flag = false ;
for ($k = 0 ; $k < $len - $i ; $k ++) {
if ($arr [$k ] > $arr [$k + 1 ]) {
$tmp = $arr [$k + 1 ];
$arr [$k + 1 ] = $arr [$k ];
$arr [$k ] = $tmp ;
$flag = true ;
}
}
if (!$flag ) return $arr ;
}
}
/*
* @param 选择排序法
* 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
* 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)
* */
php">function selectSort ($array ) {
$temp = 0 ;
for ($i = 0 ;$i < count($array ) - 1 ;$i ++){
$minVal = $array [$i ];
$minValIndex = $i ;
for ($j = $i +1 ;$j < count($array );$j ++){
if ($minVal > $array [$j ]){
$minVal = $array [$j ];
$minValIndex = $j ;
}
}
$temp = $array [$i ];
$array [$i ] = $array [$minValIndex ];
$array [$minValIndex ] = $temp ;
}
}
/*
* 插入排序 法
* 每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
* 算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。
* */
php">function insertSort ($array ) {
for ($i = 1 ;$i < count($array );$i ++){
$insertVal = $array [$i ];
$insertIndex = $i - 1 ;
while ($insertIndex >= 0 && $insertVal < $array [$insertIndex ]){
$array [$insertIndex + 1 ] = $array [$insertIndex ];
$insertIndex --;
}
if ($insertIndex + 1 !== $i ){
$array [$insertIndex + 1 ] = $insertVal ;
}
}
}
/*
* 快速排序法
* 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
* 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
* */
php">function quickSort ($array ) {
if (!isset ($array [1 ])) return $array ;
$mid = $array [0 ];
$leftArray = array ();
$rightArray = array ();
foreach ($array as $v ){
if ($v > $mid )
$rightArray [] = $v ;
if ($v < $mid )
$leftArray [] = $v ;
}
$leftArray = quickSort($leftArray );
$leftArray [] = $mid ;
$rightArray = quickSort($rightArray );
return array_merge($leftArray ,$rightArray );
}
/*
* 归并排序
* 归并排序 是指将两个或两个以上有序的数列(或有序表),合并成一个仍然有序的数列(或有序表)。
* 这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。
* */
php">function mergeSort (&$arr ) {
$len = count($arr );
mSort($arr , 0 , $len -1 );
return $arr ;
}
php">
function mSort (&$arr , $left , $right ) {
if ($left < $right ) {
$center = floor(($left +$right ) / 2 );
mSort($arr , $left , $center );
mSort($arr , $center +1 , $right );
mergeArray($arr , $left , $center , $right );
}
}
php">
function mergeArray (&$arr , $left , $center , $right ) {
$a_i = $left ;
$b_i = $center +1 ;
while ($a_i <=$center && $b_i <=$right ) {
if ($arr [$a_i ] < $arr [$b_i ]) {
$temp [] = $arr [$a_i ++];
} else {
$temp [] = $arr [$b_i ++];
}
}
while ($a_i <= $center ) {
$temp [] = $arr [$a_i ++];
}
while ($b_i <= $right ) {
$temp [] = $arr [$b_i ++];
}
for ($i =0 , $len =count($temp ); $i <$len ; $i ++) {
$arr [$left +$i ] = $temp [$i ];
}
}
php">$a = array_rand(range(1 ,10000 ), 3000 );
shuffle($a );
$t1 = microtime(true );
BubbleSort($a );
$t2 = microtime(true );
echo "冒泡排序 用时:" .(($t2 -$t1 )*1000 ).'ms' ."\n" ;
$t3 = microtime(true );
selectSort($a );
$t4 = microtime(true );
echo "选择排序用时:" .(($t4 -$t3 )*1000 ).'ms' ."\n" ;
$t5 = microtime(true );
insertSort($a );
$t6 = microtime(true );
echo "插入排序 用时:" .(($t6 -$t5 )*1000 ).'ms' ."\n" ;
$t7 = microtime(true );
quickSort($a );
$t8 = microtime(true );
echo "快速排序用时:" .(($t8 -$t7 )*1000 ).'ms' ."\n" ;
$t9 = microtime(true );
sort($a );
$t10 = microtime(true );
echo "sort排序用时:" .(($t10 -$t9 )*1000 )."ms" ."\n" ;
$t11 = microtime(true );
mergeSort($a );
$t12 = microtime(true );
echo "归并排序 用时:" .(($t12 -$t11 )*1000 )."ms" ;