數據結構——排序（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;
    }
}