<?php
$arr = array(35,66,2,15,6,81,6,9,0,-2,9); 
    /* 堆排序: 利用大（小）顶堆的特性，不断调整堆，依次选出待排序列中最大、次大值。 
    代码参考自：http://www.cnblogs.com/zemliu/archive/2012/08/18/2645941.html 
    */ 
     function heapSort(&$arr) { 
         #初始化大顶堆 为什么要初始化，其实是为了找出待排序列中最大的值 
         initHeap($arr, 0, count($arr) - 1); 
         //print_r($arr);exit; 
         #开始交换首尾节点,并每次减少一个末尾节点再调整堆,直到剩下一个元素 
         for($end = count($arr) - 1; $end > 0; $end--) {  // 依次取出大顶堆中第一个根节点即最大值，并重新调整，即 
         //依次选出次大的元素 
             $temp = $arr[0]; 
             $arr[0] = $arr[$end]; 
             $arr[$end] = $temp; 
             ajustNodes($arr, 0, $end - 1); 
         } 
     } 

     #初始化最大堆,从最后一个非叶子节点开始,最后一个非叶子节点编号为 数组长度/2 向下取整 
     function initHeap(&$arr) { 
         $len = count($arr); 
         for($start = floor($len / 2) - 1; $start >= 0; $start--) { 
             ajustNodes($arr, $start, $len - 1); 
         } 
     } 

     #调整节点 
     #@param $arr    待调整数组 
     #@param $start    调整的父节点坐标 
     #@param $end    待调整数组结束节点坐标 
     function ajustNodes(&$arr, $start, $end) { 
         $maxInx = $start; // 根节点 
         $len = $end + 1;    #待调整部分长度 
         $leftChildInx = ($start + 1) * 2 - 1;    #左孩子坐标 
         $rightChildInx = ($start + 1) * 2;    #右孩子坐标 

         #如果待调整部分有左孩子，调换左孩子与根节点，看哪个作为根节点 
         if($leftChildInx + 1 <= $len) { 
             #获取最小节点坐标 
             if($arr[$maxInx] < $arr[$leftChildInx]) { 
                 $maxInx = $leftChildInx; 
             } 
         } 
         #如果待调整部分有右子节点 ， 接上面的调整， 继续调换右孩子与根节点，看哪个作为根节点 
         if($rightChildInx + 1 <= $len) { 
             if($arr[$maxInx] < $arr[$rightChildInx]) { 
                 $maxInx = $rightChildInx; 
             } 
         } 
         // 上面调整结束后，根、左、右三个节点中，根节点一定是最大值 即maxInx是最大值的索引。 
         #交换父节点和最大节点 
         if($start != $maxInx) { 
             // 将最大值的节点调整为根节点 
             $temp = $arr[$start]; 
             $arr[$start] = $arr[$maxInx]; 
             $arr[$maxInx] = $temp; 

             #如果交换后的子节点还有子节点,继续调整 
             if(($maxInx + 1) * 2 <= $len) {// 依次反复 
                 ajustNodes($arr, $maxInx, $end); 
             } 
         } 
     } 

     $arr = array(35,66,2,15,6,81,6,9); 
     heapSort($arr); 
     print_r($arr); 
/* 
计数排序：依次计算出待排序列中每个元素比他大（小）的元素个数。然后根据这个个数依次输出即可 
得出有序的序列。缺点是：需要的空间巨大，特别是待排序列元素个数小，但是最大值却巨大的情况下， 
性能极差。 
*/ 
function count_sort($ary) { 
    $tmp = array(); 
    for($i = 0;$i< count($ary);$i++) { //第一步，需要找出最大值 
        if($max < $ary[$i]) { 
            $max = $ary[$i]; 
        } 
    } 
    for($i = 0;$i < $max;$i++) { 
        $tmp[$i] = 0; 
    } 
    for($i = 0;$i < count($ary);$i++) { 
        $tmp[$ary[$i]]++; 
    } 

    for ($i = 1; $i < count($tmp); $i++) { 
        $tmp[$i] += $tmp[$i-1]; 
    } 
    //print_r($tmp); 
    for ($i = 0; $i < count($ary); $i++) { 
        $tmp_ary[$tmp[$ary[$i]]] = $ary[$i]; 
        $tmp[$ary[$i]]--; 
    } 

    for ($i = 0; $i < count($tmp_ary); $i++) { 
        $ret[] = $tmp_ary[$i]; 
    } 
    return $ret; 
} 
$arr = array(35,66,2,15,6,81,6,44); 
print_r(count_sort($arr)); 

/* 
快速排序：经过一趟遍历，根据某一基数[一般是第一个元素]将待排序列调整为大值在右边， 
小值在左边的一个序列。按照这种方式不断递归的调整直到待排序列只剩下一个元素。 
利用分治的思想，将待排序列每次分为左边小、右边大的两个序列，并依次对各子序列进行排序。
和归并排序异同：都使用的分治的思想，先分后合。但是，快速排序经排序的过程集中在分的过程中了，
而归并排序则是将排序的过程集中在合的过程中。
*/ 
function quick_sort($ary) { 
    if(count($ary) > 1) { 
        $left = array(); 
        $right = array(); 
        $pivot = $ary[0]; 
        for($i = 1;$i< count($ary);$i++) { 
            if($ary[$i] >= $pivot) $right[] = $ary[$i]; 
            else $left[] = $ary[$i]; 
        } 

        $left = quick_sort($left); 
        $right = quick_sort($right); 
        return array_merge($left,array($pivot),$right); 
    } else { 
        return $ary; 
    } 
} 
$arr = array(35,66,2,15,6,81,6,9); 
$sort_ary = quick_sort($ary); 
print_r($sort_ary); 
/* 
快速排序第二个版本。*/ 
function partition(&$ary,$low,$high) { 
    $tmp = $ary[$low]; 
    while($low < $high) { 
        while($low < $high && $ary[$high] >= $tmp) {  
            $high--; 
        } 
        $ary[$low] = $ary[$high];// 巧妙之处: 这里只要一发生交换，下面的low就必须往前走一步
        while($low < $high && $ary[$low] <= $tmp) { 
            $low++; 
        } 
        $ary[$high] = $ary[$low];// 这里只要一发生交换，上面的high就必须往前走一步,这样一来，其实左右 
        // 调换过来的元素并没有相互覆盖掉。 
    } 
    $ary[$low] = $tmp;// 最后，需要把基数赋值给low下标，此时的low下面就是调整后次序列的分水岭，右边值大，左边值小 
    return $low; 
} 


function quick_sort2(&$ary,$low,$high) { 
    if($low < $high) { 
        $p = partition($ary,$low,$high); 
        quick_sort($ary,$low,$p - 1); 
        quick_sort($ary,$p+1,$high); 
    } 
    return $ary; 
} 
$arr = array(35,66,2,15,6,81,6,9); 
$sort_ary = quick_sort2($ary,0,count($ary)); 
print_r($sort_ary); 

/* 
/* 直接插入排序*/ 
function cr_sort1($ary) { 
    for($i = 1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i - 1;     
        while($j>=0 && $ary[$j] > $tmp) { 
            $ary[$j + 1] = $ary[$j]; 
            $j--; 
        } 
        $ary[$j+1] = $tmp; 
    } 
    return $ary; 
} 

// 插入排序另一种写法 
function cr_sort2($ary) { 
    for($i=1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i; 
        while($j >= 0 && $tmp < $ary[$j-1]) { 
            $ary[$j] = $ary[$j-1];// 往后移 
            $j--; 
        } 
        $ary[$j] = $tmp;// 插入 
    } 
    return $ary; 
} 
/*折半插入:由于普通的插入算法是依次将待排序的元素与已经完成排序的序列每一个元素做比较, 
然后插入到合适位置。二分插入的出现是为了减少元素的比较次数，本质是对插入排序的优化。 
具体思想是：利用二分查找，直接将待排序的那个元素定位到有序序列中需要插入的位置。这是优化的关键点。 
*/ 
function cr_sort3($ary) { 
    for($i = 1;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        $j = $i - 1; 
        $low = 0; 
        $high = $i - 1; 
        while($low <= $high) { 
            $mid = floor(($low + $high) / 2); 
            if($tmp > $ary[$mid]) $low = $mid + 1; 
            else  $high = $mid - 1; 
        } 

        while($j >= $low) { 
            $ary[$j + 1] = $ary[$j]; 
            $j--; 
        } 
        $ary[$low] = $tmp; 
    } 
    return $ary; 
} 
/* 
希尔排序：对插入排序的改进版。 基本算法是建立在直接插入排序算法之上的。 
基本思想是：按照某递增量，“间隔”的将待排序列调整为有序的序列。跳跃性的插入排序。 

*/ 
function shell_sort($ary) { 
    $d = count($ary); 
    while($d  > 1) { 
        $d  = intval($d / 2); //递增 
        for($i = $d;$i < count($ary);$i+=$d) { 
            $tmp = $ary[$i]; 
            $j = $i - $d;     
            while($j >= 0 && $ary[$j] > $tmp) { 
                $ary[$j + $d] = $ary[$j]; 
                $j -= $d; 
            } 
            $ary[$j+$d] = $tmp; 
        } 
    } 
    return $ary; 
} 

// 选择排序: 每次从待排序列中选出最大、次大的元素 
function xz_sort(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        $tmp = $ary[$i]; 
        for($j = $i+1;$j < count($ary);$j++) { 
            if($ary[$i] > $ary[$j]) { 
                $sit = $j; 
                $ary[$i] = $ary[$j]; 
            } 
        } 
        if($tmp != $ary[$i]) { 
            $ary[$sit] = $tmp; 
        } 
        //$ary[$i] = $flag; 
    } 
    return $ary; 
} 




$ary = array(23,-2,9,0,89,100,-23); 
$ary = cr_sort1($ary); 
print_r($ary); 
// 冒泡: 依次比较相邻的元素，两两比较，就可以最终将最大（小）的元素调整到最顶端、次顶端、、、 
// 下面的两种写法： 一是从前向后冒泡，第一次将对打元素冒到最上面、第二次冒到次下面。 
// 第二种：从后向前冒泡。 

function mp_sort2(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        for($j = 0;$j < count($ary) - $i - 1;$j++) { 
            if($ary[$j] > $ary[$j+1]) { 
                $tmp = $ary[$j]; 
                $ary[$j] = $ary[$j+1]; 
                $ary[$j+1] = $tmp; 
            } 

        } 
    } 
    return $ary; 
} 

function mp_sort(&$ary) { 
    for($i = 0;$i < count($ary);$i++) { 
        for($j = count($ary)-2;$j >= $i;$j--) { 
            if($ary[$j] > $ary[$j+1]) { 
                $tmp = $ary[$j]; 
                $ary[$j] = $ary[$j+1]; 
                $ary[$j+1] = $tmp; 
            } 
        } 
    } 
    return $ary; 
} 

// 二分查找 非递归算法 
function div_search($ary,$key) { 
    $low = 0; 
    $high = count($ary) - 1; 
    $i = 0; 
    while($low <= $high) { 
        $mid = floor(($high+$low)/2); 
        if($key == $ary[$mid]) return $key; 
        elseif($key < $ary[$mid]) $high = $mid -1;// 唯有这样，范围才会不断缩小啊 
        else $low = $mid + 1; 
    } 
} 
// 二分查找 递归算法 
function re_div_search($ary,$key,$low,$high) { 
    $mid = floor(($high+$low)/2); 
    if($key == $ary[$mid]) return $key; 
    elseif($key < $ary[$mid]) return re_div_search($ary,$key,$low,$mid -1); 
    else return re_div_search($ary,$key,$mid + 1,$high); 
} 
// 回溯法找子串 
function find_str($str,$substr) { 
    $i = 0; 
    $j =0 ; 
    while($i<strlen($str) && $j<strlen($substr)) { 
        if($str[$i]==$substr[$j]) { 
            $i++; 
            $j++; 
        } else { 
            $i = $i - $j +1; // 不相等的情况下，i是要向前走的哦！ 
            $j = 0; 
        } 
    } 
    if($j == strlen($substr)) return true; 
    return false; 
} 

$str = 'XXXhello world'; 
$substr = 'ld'; 
echo find_str($str,$substr); 
exit; 

// 斐波那契数列 
function findN($n) { 
    if($n <= 2) return 1; 
    return findN($n-2)+findN($n-1); 
} 
// 斐波那契数列的非递归形式 
function findN1($n) { 
    $arr = array(1,1); 
    if($arr <= 2) return $arr; 
    for($i = 2;$i < $n;$i++) { 
        $arr[] = $arr[$i-1] + $arr[$i-2] ; 
    } 
    return implode(',',$arr); 
} 
print_r(findN1(7));exit; 
for($i = 1;$i<=20;$i++) { 
    echo findN($i); 
    echo '<br>'; 
} 
exit; 


//$ary = array(100,1,10,10,2,8,890,4,-98,39,89,12,-2); 

//$ary = mp_sort($ary); 

//print_r($ary);