php排序算法总结

<?php
class Sort {
    //构造函数
    public function __construct() {
    }
    
    //插入排序 3k次赋值
    public function InsertSort($arr) {
        for($i = 1; $i < count ( $arr ); $i ++) {
            for($j = $i; $j > 0; $j --) {
                if ($arr [$j] < $arr [$j - 1]) {
                    $tmp = $arr [$j - 1];
                    $arr [$j - 1] = $arr [$j];
                    $arr [$j] = $tmp;
                }
            }
        }
        return $arr;
    }
    
    //改进的插入排序 K+2次赋值
    public function InsertImprovedSort($arr) {
        for($i = 1; $i < count ( $arr ); $i ++) {
            $tmp = $arr [$i];
            $j = $i - 1;
            while ( $arr [$j] > $tmp ) {
                $arr [$j + 1] = $arr [$j];
                $arr [$j] = $tmp;
                $j --;
            }
        }
        return $arr;
    }
    
    //二分插入排序
    public function InsertBinarySort($arr) {
        for($i = 1; $i < count ( $arr ); $i ++) {
            $tmp = $arr [$i];
            $left = 0;
            $right = $i - 1;
            while ( $left <= $right ) {
                $middle = floor ( ($left + $right) / 2 );
                if ($arr [$middle] < $tmp) {
                    $left = $middle + 1;
                } else {
                    $right = $middle - 1;
                }
            }
            for($j = $i - 1; $j >= $left; $j --) {
                $arr [$j + 1] = $arr [$j];
            }
            $arr [$left] = $tmp;
        }
        return $arr;
    }
    
    //冒泡排序
    public function BubbleSort($arr) {
        for($i = 1; $i < count ( $arr ); $i ++) {
            for($j = count ( $arr ) - 1; $j > $i; $j --) {
                if ($arr [$j] < $arr [$j - 1]) {
                    $tmp = $arr [$j - 1];
                    $arr [$j - 1] = $arr [$j];
                    $arr [$j] = $tmp;
                }
            }
        }
        return $arr;
    }
    
    //改进的冒泡排序
    public function BubbleImprovedSort($arr) {
        for($i = 1; $i < count ( $arr ); $i ++) {
            $noswap = true;
            for($j = count ( $arr ) - 1; $j > $i; $j --) {
                if ($arr [$j] < $arr [$j - 1]) {
                    $tmp = $arr [$j - 1];
                    $arr [$j - 1] = $arr [$j];
                    $arr [$j] = $tmp;
                    $noswap = false;
                }
            }
            if ($noswap) {
                return $arr;
            }
        }
    }
    
    //选择排序
    public function SelectSort($arr) {
        for($i = 0; $i < count ( $arr ) - 1; $i ++) {
            $min = $i;
            for($j = $i + 1; $j < count ( $arr ); $j ++) {
                if ($arr [$min] > $arr [$j]) {
                    $min = $j;
                }
            }
            $tmp = $arr [$min];
            $arr [$min] = $arr [$i];
            $arr [$i] = $tmp;
        }
        return $arr;
    }
    
    //shell排序...借助直接插入排序算法
    public function toggle_sort(&$a) {
        $i = 0;
        $lastindex = count ( $a ) - 1;
        while ( $i < $lastindex ) {
            if ($a [$i] <= $a [$i + 1]) {
                $i ++;
            } else {
                $tmp = $a [$i];
                $a [$i] = $a [$i + 1];
                $a [$i + 1] = $tmp;
                if ($i) {
                    $i --;
                }
            }
        }
    }
   
    //桶排序
    public function TongSort($arr) {
        $arrTemp = array (); //临时数组
        $len = count ( $arr ); //数组元素长度
        //将数组赋值到临时数组中
        for($i = 0; $i < $len; $i ++) {
            $arrTemp [$i] = $arr [$i];
        }
        //初始化数组各元素个数为0
        for($i = 0; $i < $len; $i ++) {
            $cnt [$i] = 0;
        }
        //统计数组个元素的个数
        for($i = 0; $i < $len; $i ++) {
            $cnt [$arrTemp [$i]] ++;
        }
        //计算数组元素各元素应该呆的位置
        for($i = 1; $i < $len; $i ++) {
            $location [$i] = $location [$i - 1] + $cnt [$i];
        }
        //还原数组
        for($i = 0; $i < $len; $i ++) {
            $arr [-- $location [$arrTemp [$i]]] = $arrTemp [$i];
        }
        return $arr;
    }
    
    //获取指点文件夹下所有子文件及其文件
    public function getdirpath($path) {
        $data = array ();
        if (is_dir ( $path )) {
            if (($dh = opendir ( $path )) != false) {
                while ( ($file = readdir ( $dh )) !== false ) {
                    if ($file != "." || $file != "..") {
                        $data [] = $file;
                    }
                }
                closedir ( $dh );
            }
        }
    }
}
$arr = array ('7654', '6768', '9297', '7657', '6715', '9879', '6546', '6543', '9871' );
$sort = new Sort ();
$sort->BaseSort ( $arr );

?>