class test{  
 public function main()
    {

        $data = $this->createData();
        $this->bubbleSort($data);
        $this->selectSort($data);
        $this->insertSort($data);
        $this->shellSort($data);
        $this->mergeSort($data);
        $this->heapSort($data);
        $this->fastSort($data);
    }

    public function createData()
    {
        $firtime = microtime();
        $data = [];
        for($i = 0; $i < 1000000;){
            $val = ceil(rand(1,1000000));
            if(!in_array($val, $data)){
                $data[] = $val;
                $i++;
            }
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
        return $data;
    }

    //归并排序开始
    public function mergeSort($data)
    {
        $firtime = microtime();
        $res = $this->mergeSortMain($data, 0, count($data)-1);
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }

    public function mergeSortMain(&$data, $from, $to){
        if($from == $to){
            return [$data[$to]];
        }
        $middle = floor(($to + $from)/2);
        $left = $this->mergeSortMain($data, $from, $middle);
        $right = $this->mergeSortMain($data, $middle+1, $to);
        $res = $this->sortTwoSortArr($left, $right);
        return $res;
    }

    public function sortTwoSortArr($arrA, $arrB){
        $res = [];
        $index = 0;
        $indexA = 0;
        $indexB = 0;
        while (count($arrA)&&count($arrB)) {
            if ($arrA[$indexA] < $arrB[$indexB]) {
                $res[$index++] =  $arrA[$indexA];
                unset($arrA[$indexA++]);
            } else {
                $res[$index++] =  $arrB[$indexB];
                unset($arrB[$indexB++]);
            }
        }
        if (count($arrA)) {
            while (count($arrA)) {
                $res[$index++] =  $arrA[$indexA];
                unset($arrA[$indexA++]);
            }
        } elseif (count($arrB)){
            while (count($arrB)) {
                $res[$index++] =  $arrB[$indexB];
                unset($arrB[$indexB++]);
            }
        }
        return $res;
    }
    //归并排序结束

    //快速排序开始
    public function fastSort($data)
    {
        $firtime = microtime();
        $this->fastSortMain(0, count($data) - 1, $data);
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }

    public function fastSortMain($start, $end, &$data){
        if ($start >= $end) {
            return;
        }
        $middle = $this->fastSortSwap($start, $end, $data);
        $this->fastSortMain($start, $middle-1, $data);
        $this->fastSortMain($middle+1, $end, $data);
    }


    //这个方法的作用是把 $data从start到end之间的部分 分成大于某值或者小于某值两部分，并且返回某值的位置
    public function fastSortSwap($start, $end, &$data){
        $flag = $data[$end];
        $resust_key = $start;
        for ($i=$start; $i < $end; $i++) { 
            if ($data[$i] > $flag) {
                continue;
            } else {
                $temp = $data[$i];
                $data[$i] = $data[$resust_key];
                $data[$resust_key++] = $temp;
            }
        }
        $data[$end] = $data[$resust_key];
        $data[$resust_key] = $flag;
        return $resust_key;
    }
    //快速排序结束
    
    //选择排序开始
    public function selectSort($data)
    {
        $firtime = microtime();
        for ($i=0; $i <count($data) ; $i++) {
            $minval = $data[$i];
            $minkey = $i;
            for ($j=$i; $j < count($data); $j++) { 
                if($data[$j]<$minval){
                    $minval = $data[$j];
                    $minkey = $j;
                }
            }
            $temp = $data[$i];
            $data[$i] = $minval;
            $data[$minkey] = $temp;
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }
    //选择排序结束
    
    //希尔排序开始
    public function shellSort($data)
    {
        $firtime = microtime();
        $jump = floor(count($data)/2);
        while($jump >= 1){
            for ($i = 0; $i < $jump; $i++) {
                for ($j = $i + $jump; $j < count($data);) {
                    $temp = $data[$j];
                    $k = $j - $jump;
                    while ($k >= 0&&$data[$k] > $temp) {
                        $data[$k + $jump] = $data[$k];
                        $k = $k - $jump;
                    }
                    $data[$k + $jump] = $temp;
                    $j += $jump;
                }
            }
            $jump = floor($jump/2);
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }
    //希尔排序结束
    
    //冒泡排序开始
    public function bubbleSort($data)
    {
        $firtime = microtime();
        for ($i = count($data)-1; $i > 0; $i--) {
            $flag = true;
            for ($j=0; $j < $i; $j++) { 
                if($data[$j] > $data[$j+1]){
                    $temp = $data[$j];
                    $data[$j] = $data[$j+1];
                    $data[$j+1] = $temp;
                    $flag = false;
                }
            }
            if($flag){
                break;
            }
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }
    //冒泡排序结束
    
    //插入排序开始
    public function insertSort($data){
        $firtime = microtime();
        for ($i = 1; $i < count($data); $i++) {
            $temp = $data[$i];
            $j = $i - 1;
            while ($j > 0&&$data[$j] > $temp) {
                $data[$j+1] = $data[$j];
                $j--;
            }
            $data[$j+1] = $temp;
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }
    //插入排序结束
    
    //堆排序开始

    public function heapSort($data){
        $firtime = microtime();
        $this->initHeap($data);
        $n = count($data);
        for ($i = $n - 1; $i > 0; $i--) { 
            $this->swap($data, 0, $i);
            $this->down($data, 0, $i - 1);
        }
        $sectime = microtime();
        $this->getTimeLimit($firtime, $sectime);
    }

    public function initHeap(&$data){
        $n = count($data);
        for ($i = $n/2-1; $i >= 0; $i--) { 
            $this->down($data, $i, $n-1);
        }
    }

    public function swap(&$data, $i, $j){
        $n = count($data);
        if ($i < 0||$j < 0||$i > $n||$j > $n) {
            return;
        } else {
            $temp = $data[$i];
            $data[$i] = $data[$j];
            $data[$j] = $temp;
        }
    }

    public function down(&$data, $head, $tail){
        $left_child = $head * 2 + 1;
        $right_child = $left_child + 1;
        $next_head = $left_child;
        $head_val = $data[$head];
        while ($left_child <= $tail) {
            if ($right_child <= $tail&&$data[$right_child] > $data[$left_child]) {
                $next_head = $right_child;
            }
            if ($data[$next_head] > $head_val) {//无论何时都只和最上面的那个值比较
                $data[$head] = $data[$next_head];
            } else {
                break;
            }
            $head = $next_head;
            $left_child = $head * 2 + 1;
            $right_child = $left_child + 1;
            $next_head = $left_child;
        }
        $data[$head] = $head_val;
    }
    //堆排序结束
    
    //获取花费时间开始
    public function getTimeLimit($a, $b){
        list($seconds1, $msecond1) = explode(' ', $a);
        list($seconds2, $msecond2) = explode(' ', $b);
        var_dump(($seconds2 - $seconds1)+($msecond2 - $msecond1));
    }
    //获取话费时间结束
}