<?php
/**
 * 各种排序
 * @author zhaojaingwei
 * @since 2011/11/21 16:14
 *
 */

$list = array(3,5,1,2,10,8,15,19,20);

//快排
function fast(&$list, $low, $high){
    if($high - $low > 5){
        while($low < $high){
            $key = excute($list, $low, $high);
            fast($list, $low, $key - 1);
            //fast($list, $key + 1, $high);//普通递归实现
            $low = $key + 1;//尾递归实现
        }
    }else{
        insert($list);
    }
}

//快排执行一次排序
function excute(&$list, $low, $high){
    swap($list, $low, ($low + $high)/2);
    $temp = $list[$low];
    while($low < $high){
        while($low < $high && $list[$high] > $temp){
            $high --;
        }

        $list[$low] = $list[$high];

        while($low < $high && $list[$low] < $temp){
            $low ++;
        }
        
        $list[$high] = $list[$low];
    }

    $list[$low] = $temp;

    return $low;
}

//堆排序
function heap(&$list){
    buildHeap($list);
    for($i = count($list) - 1; $i > 0; $i --){
        swap($list, $i, 0);
        heapfy($list, 0, $i - 1); 
    }
}

//创建堆
function buildHeap(&$list){
    for($i = (count($list) - 2)/2; $i >= 0; $i --){
         heapfy($list, $i, count($list) - 1);  
    }
}

//维护堆
function heapfy(&$list, $low, $high){
    $temp = $list[$low];

    for($i = ($low * 2 + 1); $i <= $high; $i = ($i * 2 + 1)){
        if($i < $high && $list[$i] < $list[$i + 1]){
            $i ++;   
        }

        if($temp < $list[$i]){
            swap($list, $i, $low);
            $low = $i;
        }else{
            break;
        }

    }

    $list[$low] = $temp;
}

//希尔排序
function shell(&$list){
    $a = 0;
    $code = count($list)/3 + 1;
    while($code >= 1){
        for($i = $code; $i < count($list); $i ++){
            $a ++;
            if($list[$i] < $list[$i - $code]){
                $temp = $list[$i];
                $list[$i] = $list[$i - $code];
                $j = $i - 2*$code;
                
                for(; $j >= 0 && $list[$j] > $temp; $j -= $code){
                    $list[$j + $code] = $list[$j];
                    $a ++; 
                }
                $list[$j + $code] = $temp;
            }
        }

        $code = $code/3;
    }

    echo $a;
}

//直接插入排序
function insert(&$list){
    $a = 0;
    for($i = 1; $i < count($list); $i ++){
        $a ++;
        if($list[$i] < $list[$i - 1]){
            $temp = $list[$i];
            $list[$i] = $list[$i - 1];
            
            $j = $i - 2; 
            for(; $list[$j] > $temp; $j --){
                $a ++;
                $list[$j + 1] = $list[$j]; 
            }
            
            $list[$j + 1] = $temp;
        }
    }

    echo $a;
}

//简单选择排序
function select(&$list){
    $a = 0;
    for($i = 0; $i < count($list); $i ++){
        $min = $i;
        $a ++;
        for($j = $i + 1; $j < count($list); $j ++){
            $a ++;
            if($list[$j] < $list[$min]){
                $min = $j;
            }
        }
    
        if($min != $i)
            swap($list, $i, $min);
    }
    echo $a;
}

//冒泡排序
function bubble(&$list){
    $swap = TRUE;
    $a = 0;
    for($i = 0; $i < count($list) && $swap; $i ++){
        $swap = FALSE;
        $a ++;
        for($j = count($list) - 2; $j >= $i; $j --){
            $a ++;
            if($list[$j] > $list[$j + 1]){
                $swap = TRUE;
                swap($list, $j, $j + 1);
            }
        }
    }
    echo $a;
}

//移动或交换函数
function swap(&$list, $i, $j){
    $temp = $list[$i];
    $list[$i] = $list[$j];
    $list[$j] = $temp;
}

?>