编程过程中经常用到的算法

一、选择排序

        选择排序是通过每一趟排序过程中从待排序记录中选择出关键字最小（大）的记录，将其依次放在数据表的最前或最后端的方法来实现整个数据表的有序排列

function selectSort(&$arr)
{
    $len = count($arr);
    for($i=0;$i<$len;$i++){
        $location = $i;
        for($j=$i+1;$j<$len;$j++){
            if($value > $arr[$j]){
                $location = $j;
            }
        }

        if($location != $i){
            $change = $arr[$i];
            $arr[$i] = $arr[$location];
            $arr[$location] = $change;
        }

    }
}
           

二、快速排序

        通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quickSort($arr)
{
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $key = $arr[0];
    $left = array();
    $right = array();
    for($i=1;$i<$len; $i++){
        $val = $arr[$i];
        if($val <= $key){
            $left[] = $val;
        }else{
            $right[] = $val;
        }
    }

    $left = quickSort($left);
    $right = quickSort($right);
    return array_merge($left,array($key),$right);
    
}
           

三、插入排序

       通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入

function insertSort(&$arr)
{
    for($i=1;$i<count($arr);$i++){
        if($arr[$i-1] > $arr[$i]){
            $temp = $arr[$i];
            $j = $i;
            while($j>0 && $arr[$j-1] > $temp){
                $arr[$j] = $arr[$j-1];
                $j--;
            }
            $arr[$j] = $temp;
        
        }
    
    }

}
           

四、堆排序

        堆排序是指利用堆这种数据结构所设计的一种排序。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。

function exchange(&$a,&$b){
        $temp = $b;
        $b = $a;
        $a = $temp;
}

function left($i){ return $i*2+1;}
function right($i){ return $i*2+2;}

function buildHeap(&$array,$i,$heapsize){

        $left = left($i);
        $right = right($i);
        $max = $i;
        if($i < $heapsize && $left<$heapsize  && $array[$left] > $array[$i] ){
                $max = $left;
        }

        if($i < $heapsize && $right<$heapsize && $array[$right] > $array[$max]){
                $max = $right;
        }
        if($i != $max && $i < $heapsize && $max < $heapsize){

                exchange($array[$i],$array[$max]);
                buildHeap($array,$max,$heapsize);

        }
}

function sortHeap(&$array,$heapsize){
        while($heapsize){
                exchange($array[0],$array[$heapsize-1]);
                $heapsize = $heapsize -1;
                buildHeap($array,0,$heapsize);
        }
}

function createHeap(&$array,$heapsize){
        $i = ceil($heapsize/2)-1;
        for(;$i>=0;$i--){
                buildHeap($array,$i,$heapsize);
        }
}

function main(){
        $array = array(88,99,22,11,22,13,9,2,1,100,12);
        $heapsize = count($array);
        createHeap($array,$heapsize);
        sortHeap($array,$heapsize);
}
           

五、冒泡排序

        冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

function bubbleSort(&$arr)
{
    $len = count($arr);
    for($i=0;$i<$len;$i++){
        for($j=$i+1;$j<$len;$j++){
            if($arr[$i] > $arr[$j]){
                $temp = $arr[$i];
                $arr[$i] = $arr[$j];
                 $arr[$j] = $temp;
             }
         }
    }
}
           

六、归并排序

        归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。概念不好理解，见下图：

function merge(&$arr,$start,$mid,$end)
{
    $i = $start;
    $j = $mid + 1;
    $k = 0;
    $newArr = array();
    while($i <= $mid && $j<= $end){
        if($arr[$i] <= $arr[$j]){
           $newArr[$k++] = $arr[$i++]; 
        }else{
           $newArr[$k++] = $arr[$j++];
        }
    }
    while($i <= $mid ){
        var_dump($k);
        $newArr[$k++] = $arr[$i++];
    }

    while($j <= $end ){
        var_dump($k);
        $newArr[$k++] = $arr[$j++];
    }
    for($i=0;$i<$k;$i++){
        $arr[$i+$start] = $newArr[$i];
    }

}

function mergeSort(&$arr,$low,$high)
{
    if($low < $high){
        $mid = floor(($low+$high)/2);
        mergeSort($arr,$low,$mid);
        mergeSort($arr,$mid+1,$high);
        merge($arr,$low,$mid,$high);
    }
}
           

各个排序算法的时间复杂度如下：