数据结构——排序（php代码实现）

<?php
/**
 * BubbleSort0($arr):冒泡排序
 * BubbleSort1($arr):冒泡排序——优化
 * BubbleSort2($arr):冒泡排序——另一种实现方法
 * SelectSort($arr):选择排序
 * InsertSort($arr):插入排序
 * ShellSort($arr):希尔排序
 */
class Sort{

    /**
     * 冒泡排序:指的是两两相邻的数据直接进行的比较交换排序
     * @param $arr 要进行排序的数组
     */
    public static function BubbleSort0($arr){
        for($i=0;$i<count($arr)-1;$i++){
            for($j=1;$j<count($arr);$j++){
                if($arr[$j-1]<$arr[$j]){ //从大到小排序
                    $temp=$arr[$j-1];
                    $arr[$j-1]=$arr[$j];
                    $arr[$j]=$temp;
                }
            }
        }
        return $arr;
    }

    //此算法是对上面算法的优化
    //避免了对已经有序的数据进行的比较
    public static function BubbleSort1($arr){
        $flag=true;
        for($i=0;$i<count($arr)-1 && $flag;$i++){
            $flag=false;
             for($j=1;$j<count($arr);$j++){
                if($arr[$j-1]<$arr[$j]){ //从大到小排序
                    $temp=$arr[$j-1];
                    $arr[$j-1]=$arr[$j];
                    $arr[$j]=$temp;
                    $flag=true;
                }
            }
        }
    }

    //此算法，前面的一个数据依次与后面的所有数据进行比较，更加大小再进行交换。严格意义上不算是冒泡排序
    public static function BubbleSort2($arr){
        for($i=0;$i<count($arr)-1;$i++){
            for($j=$i+1;$j<count($arr);$j++){
                if($arr[$i]<$arr[$j]){
                    $temp=$arr[$i];
                    $arr[$i]=$arr[$j];
                    $arr[$j]=$temp;
                }
            }
        }
        return $arr;
    }

    /**
     * 简单选择排序:就是先取出第一个（每次循环的第一个），假设其下标所在的数据时最小的，然后再依次与后面的数据比较找出最小的数据元素的下标，最后在进行交换。
     * @param $arr
     */
    public static 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;
                }
            }
            if($min != $i){
                $temp=$arr[$min];
                $arr[$min]=$arr[$i];
                $arr[$i]=$temp;
            }
        }
    }

    /**
     * 直接插入排序：就是在一个有序的数据集合中，通过与集合中的元素进行比较，然后插入数据。
     * @param $arr
     */
    public static function InsertSort($arr){
        for($i=1;$i<count($arr);$i++){
            $inserted=$arr[$i]; //先假设数组只有一个元素并且默认它已经是有序的（因为只有一个嘛），然后取出第二个元素作为插入的元素
            //$j=$i-1:要插入元素的前一个数据元素下标
            //$j>=0 && $inserted < $arr[$j]:将当前要插入的元素依次与其前面的元素进行比较，若要插入的元素比其前面的元素小，那么其前面的元素就要往后移动一位，以为要插入的元素腾出位置
            for($j=$i-1;$j>=0 && $inserted<$arr[$j];$j--){
                $arr[$j+1]=$arr[$j];
            }
            $arr[$j+1]=$inserted; //表示要插入元素的位置下标为$j+1，因为for循环最后又执行了一次$j--，所以要把减去的 1 加上
        }
        return $arr;
    }

    /**
     * 希尔排序:将一个待排序的数组，分成若干子序列，然后分别对其进行排序，使其先部分有序，如此循环，最后得到有序数组。
     * 它是对直接插入排序的一种改进。
     * @param $arr
     * @return mixed
     */
    public static function ShellSort($arr){
        $count=count($arr);
        for($inc=floor($count/3);$inc>0;$inc=floor($inc/3)){
            for($i=$inc;$i<$count;$i++){
                $instered=$arr[$i];
                for($j=$i-$inc;$j>=0 && $instered<$arr[$j];$j-=$inc){
                    $arr[$j+$inc]=$arr[$j];
                }
                $arr[$j+$inc]=$instered;
            }
        }
        return $arr;
    }
}