<?php

//冒泡排序

//原理:从倒数第一个数开始,相邻的两个数比较,后面比前面的小,则交换位置,一直到比较第一个数之后则最小的会排在第一位,以此类推

function bubble_sort($arr){

    $count = count($arr);

    for($i=0; $i<$count; $i++){

        for($j=$count-1; $j>$i; $j--){

            if($arr[$j]<$arr[$j-1]){

                $tmp = $arr[$j];

                $arr[$j] = $arr[$j-1];

                $arr[$j-1] = $tmp;

            }

        }

    }

    return $arr;

}

//快速排序

function quick_sort($arr){

    $count = count($arr);

    if($count<=1)return $arr;

    $key = $arr[0];

    $l = array();

    $r = array();

    for($i=1;$i<$count;$i++){

        if($arr[$i]<=$key){

            $l[] = $arr[$i];

        }else{

            $r[] = $arr[$i];

        }

    }

    $l = quick_sort($l);

    $r = quick_sort($r);

    return array_merge($l,array($key),$r);

}

//选择排序

//原理:利用数组的key,假设数组的第一个key[0]为最小的,和后面的数比较,如果key[0]大于后面的数则存起来key,比较完之后(比较到数组的最后一个),如果key[0]!=存起来的key,则交换他们的key. 以此类推, 然后再从第二个key[1]去和后面的比较

function select_sort($arr){

    $count = count($arr);

    for($i=0;$i<$count;$i++){

        $k = $i;

        for($j=$i+1;$j<$count;$j++){

            if($arr[$j]<$arr[$k]){

                $k = $j;

            }

        }

        if($k != $i){

            $tmp = $arr[$k];

            $arr[$k] = $arr[$i];

            $arr[$i] = $tmp;

        }

    }

    return $arr;

}

//插入排序

//原理:假设一堆数字都排好序了,[6,7,8] 现在给你一个9让你插进去,这个时候9和8比大,就放到8后面就行了,[6,7,8,9],因为一堆数字排好序了, 前面的肯定都比8小, 所以就不用和前面的比较了.

function insert_sort($arr){

    $count = count($arr);

    for($i=1; $i<$count; $i++){

        $tmp = $arr[$i];

        $j = $i-1;

        while($arr[$j]>$tmp){

            $arr[$j+1] = $arr[$j];

            $arr[$j] = $tmp;

            $j--;

            if($j<0){

                break;

            }

        }

    }

    return $arr;

}

//打印结果

function display($function,$a){

    $t1 = microtime(true);

    $arr = $function($a);

    $t2 = microtime(true);

    // print_r($arr);

    return $t2-$t1;

}

//随机产生1600长度数组;

$a = array_rand(range(1,2000),1600);

//打乱数组

shuffle($a);

echo "<pre>";

echo '冒泡排序 ',display('bubble_sort',$a),'</br>';

echo '快速排序 ',display('quick_sort',$a),'</br>';

echo '选择排序 ',display('select_sort',$a),'</br>';

echo '插入排序 ',display('insert_sort',$a),'</br>';