<?php

header("content-type:text/html;charset=utf-8");


$testArr = array();
$time1 = microtime(true);
$testArr = range(1, 10);
$dataLen = count($testArr);
shuffle($testArr);
echo '生成并打乱数组花费时间为:'.(microtime(true) - $time1).'<br>';
//1.冒泡排序
$time1 = microtime(true);
mpsort($testArr);
echo '冒泡排序运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'<br>';
//2.简单排序
$time1 = microtime(true);
simpleSort($testArr);
echo '简单排序运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'<br>';
//3.插入排序
$time1 = microtime(true);
insertSort($testArr);
echo '插入排序运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'<br>';
//4.希尔排序
 $time1 = microtime(true);
$memory1 = memory_get_usage(true);
sellSort($testArr);
$maxMemory = memory_get_peak_usage(true);
echo '希尔排序运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'分配存储空间为:'.(memory_get_usage(true) - $memory1).'峰值为:'.$maxMemory.'<br>'; 
//5.快速排序
$time1 = microtime(true);
$memory1 = memory_get_usage(true);
testQuickSort($testArr);
$maxMemory = memory_get_peak_usage(true);
echo '快速排序运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'分配存储空间为:'.(memory_get_usage(true) - $memory1).'峰值为:'.$maxMemory.'<br>';
//6.快速排序(调用函数)
$time1 = microtime(true);
$memory1 = memory_get_usage(true);
testQuickSort2($testArr);
$maxMemory = memory_get_peak_usage(true);
echo '快速排序(调用函数)'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'分配存储空间为:'.(memory_get_usage(true) - $memory1).'峰值为:'.$maxMemory.'<br>';
//内置函数
$time1 = microtime(true);
sort($testArr);
$maxMemory = memory_get_peak_usage(true);
echo '内置函数运行'.$dataLen.'次花费时间为:'.(microtime(true) - $time1).'分配存储空间为:'.(memory_get_usage(true) - $memory1).'峰值为:'.$maxMemory.'<br>';
//冒泡排序
function mpsort($testArr){
    
    echo '冒泡排序:<br>';
    echo '排序前:';
    iteratorArr($testArr);
    $dataLen = count($testArr);
    for($i=0;$i<$dataLen-1;$i++){
        for($j=0;$j<$dataLen-1-$i;$j++){
            
            if($testArr[$j] > $testArr[$j+1]){
                $maxVal       = $testArr[$j];
                $testArr[$j]  = $testArr[$j+1];
                $testArr[$j+1]= $maxVal;
            }
            
        }
    }
    
    echo '排序后:';
    iteratorArr($testArr);
}

//选择排序（简单排序）
function simpleSort($testArr){
    echo '简单排序:<br>';
    echo '排序前:';
    iteratorArr($testArr);
    $dataLen = count($testArr);
    $index   = 0;
    $minVal  = 0;
    for($i=0;$i<$dataLen;$i++){
        $index   = $i;
        for($j=$i;$j<$dataLen;$j++){
            if($testArr[$index] > $testArr[$j]) $index = $j; 
        }
        
        $minVal = $testArr[$index];
        $testArr[$index] = $testArr[$i];
        $testArr[$i]     =  $minVal;
    }
    
    
    echo '排序后:';
    iteratorArr($testArr);
}

//插入排序
function insertSort($testArr){
    echo '插入排序:<br>';
    echo '排序前:';
    iteratorArr($testArr);
    
    $dataLen = count($testArr);
    $index   = 0;
    $tmp     = 0;
    //print_r($testArr);
    for($i=1;$i<$dataLen;$i++){
       
       if($testArr[$i-1] < $testArr[$i]) continue;
       $index = $i;
       while($index >=1 && $testArr[$index] < $testArr[$index-1]){
           soapArr($testArr , $index , $index-1);
           $index--;
       }
    }
    
    echo '排序后:';
    iteratorArr($testArr);
}

//希尔排序
function sellSort($testArr){
    echo '希尔排序:<br>';
    echo '排序前:';
    iteratorArr($testArr);
    
    $dataLen = count($testArr);
    $index   = 0;
    $tmp     = 0;
    $increment = intval($dataLen/2);
    
    for($k =$increment; $k>=1 ;$k--){
        
        for($i=$k;$i<$dataLen;$i += $k){
            
            if($testArr[$i-$k] < $testArr[$i]) continue;
            $index = $i;
            while($index >=1 && $testArr[$index] < $testArr[$index-$k]){
                //soapArr($testArr , $index , $index-$k);
                $tmp = $testArr[$index];
                $testArr[$index] = $testArr[$index-$k];
                $testArr[$index-$k] = $tmp;
                $index-=$k;
            }
            
        }
        
    }
    
    echo '排序后:';
    iteratorArr($testArr);
}

function testQuickSort($testArr){
    echo '快速排序:<br>';
    echo '排序前:';
    iteratorArr($testArr);
    
    quickSort($testArr , 0 , count($testArr));
    
    echo '排序后:';
    iteratorArr($testArr);
}


//快速排序
function quickSort(&$testArr , $start , $end){
   
   
   
    $index = $start+1;
    if($index > $end) return $testArr;
    $tmp = 0;
    $compareVal = $testArr[$start];
    for($i=$index;$i<$end;$i++){
        
        if($testArr[$i] < $compareVal){
            //soapArr($testArr , $index , $i);
            $tmp = $testArr[$index];
            $testArr[$index] = $testArr[$i];
            $testArr[$i] = $tmp;
            $index++;
        }
    }

    //soapArr($testArr , $start , $index-1);
    $tmp = $testArr[$start];
    $testArr[$start] = $testArr[$index-1];
    $testArr[$index-1] = $tmp;
    quickSort($testArr , $start , $index-1);
    quickSort($testArr, $index, $end);
}

//快速排序
function quickSort2(&$testArr , $start , $end){
    
    
    
    $index = $start+1;
    if($index > $end) return $testArr;
    $tmp = 0;
    $compareVal = $testArr[$start];
    for($i=$index;$i<$end;$i++){
        
        if($testArr[$i] < $compareVal){
            soapArr($testArr , $index , $i);
            $index++;
        }
    }
    
    soapArr($testArr , $start , $index-1);
   
    quickSort2($testArr , $start , $index-1);
    quickSort2($testArr, $index, $end);
}

function testQuickSort2($testArr){
    echo '快速排序(调用函数):<br>';
    echo '排序前:';
    iteratorArr($testArr);
    
    quickSort($testArr , 0 , count($testArr));
    
    echo '快速排序(调用函数)';
    iteratorArr($testArr);
}

//交换数组
function soapArr(&$arr , $a , $b){
    $tmp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $tmp;
}

//遍历器
function iteratorArr($arr){
  
    foreach($arr as $v){
        echo $v."\n\r";
    }
    echo "<br>";
}