<?php
class Sort{
    /**
     * 一、冒泡排序：
     *  思路：
     *      1. 循環(huán) n-1 個位置，對于每個位置 i，都和 [i+1,n] 的每個位置 j 上的數(shù)對比
     *      2. 如果位置 i 上的數(shù)大于（小于）位置 j 上的數(shù)，交換這兩個位置上的數(shù)
     *      3. 使得對比完成后，第 i 個位置上存放了第 i ?。ù螅┑臄?shù)
     *  分析：
     *      1. 時間復雜度 O(n^2)，空間復雜度 O(1)
     *      2. 由于大小相同的數(shù)并沒有交換位置，因此屬于：穩(wěn)定排序
     * @param array $data
     * @return array
     */
    public static function bubbleSort(&$data=[]){
        if(!is_array($data)){
            return $data;
        }
        $data_size = count($data);
        if(0 == $data_size){
            return $data;
        }
        for($i=0; $i<$data_size-1; $i++){
            for($j=$i+1; $j<$data_size; $j++){
                if($data[$i] > $data[$j]){
                    $temp = $data[$i];
                    $data[$i] = $data[$j];
                    $data[$j] = $temp;
                }
            }
        }
        return $data;
    }

    /**
     * 二、選擇排序：
     *  思路：
     *      1. 對于長度為 n 的待排序數(shù)組，將數(shù)組分為兩部分：排好序的和未排好序的，即：(1, i) 和 (i+1, n)
     *      2. 選擇排序過程是：不斷增大排序好的部分，減小未排序號的部分，直接全部排序好。
     *      3. 不斷增大排序好的部分的過程是：每次從未排好序的部分中，選擇最?。ㄗ畲螅┑囊粋€，放在排好序的部分的末尾，也是未排好序的部分的開頭
     *      4. 與冒泡排序不同的是：在不斷增大排序好的部分的過程中，交換只發(fā)生一次，即：未排好序的第一個位置和未排好序本分的最?。ㄗ畲螅┑奈恢媒粨Q。
     *  分析：
     *      1. 時間復雜度 O(n^2)，空間復雜度 O(1)
     *      2. 由于大小相同的數(shù)并沒有交換位置，因此屬于：穩(wěn)定排序
     * @param $data
     * @return array
     */
    public static function selectionSort(&$data){
        if(!is_array($data)){
            return $data;
        }
        $data_size = count($data);
        if(0 == $data_size){
            return $data;
        }
        for($i=0; $i<$data_size-1; $i++){
            $min_index = $i;
            for($j=$i+1; $j<$data_size; $j++){
                if($data[$min_index] > $data[$j]){
                    $min_index = $j;
                }
            }
            if($min_index != $i){
                $temp = $data[$i];
                $data[$i] = $data[$min_index];
                $data[$min_index] = $temp;
            }
        }
        return $data;
    }

    /**
     * 三、插入排序：
     *  思路：
     *      1. 還是將長度為 n 的待排序數(shù)組分成：已排序的 (1, i) 和 未排序的 (i+1, n)
     *      2. 對于未排序部分中的第一個元素，在已排序的部門中，找到一個合適的位置
     *      3. 將已排序部門中這個位置及以后的元素后移一位，然后將未排序部分中的第一個元素放在這個位置
     *      4. 增加已排序部門的長度，縮短未排序排序的長度，直到未排序部門長度為0
     *  分析：
     *      1. 時間復雜度 O(n^2)，空間復雜度 O(1)
     *      2. 穩(wěn)定排序。即：大小相同的數(shù)從未排序部門轉移到已經(jīng)排序部分的過程中，未改變其相對位置。
     * @param $data
     * @return array
     */
    public static function insertionSort(&$data){
        if(!is_array($data)){
            return $data;
        }
        $data_size = count($data);
        if(0 == $data_size){
            return $data;
        }
        for($i=0; $i<$data_size-1; $i++){
            $new_item = $data[$i + 1];
            $ins_index = $i;
            while($ins_index >= 0 && $new_item < $data[$ins_index]){
                $data[$ins_index + 1] = $data[$ins_index];
                $ins_index = $ins_index - 1;
            }
            $data[$ins_index+1] = $new_item;
        }
        return $data;
    }

    /**
     * 四、希爾排序
     *  希爾排序是基于插入排序優(yōu)化過后的、一種時間復雜度小于 O(n^2) 的插入排序
     *  思路：
     *      1. 將整個待排序數(shù)組進行分組，每次保證：組內有序
     *      2. 不斷的縮短《每組》的長度，直到為 1，即：完成排序。
     *      3. 依舊使用插入排序的排序方法：計算待排序元素的位置，后移這個位置及以后的元素，將待排序元素放到這個位置上，直到待排序部分的長度為 0
     *  分析：
     *      1. 時間復雜度 O(nlog2n)，空間復雜度 O(1)
     *          * while1 - for1 - while2
     *          * while1 的時間復雜度是 O(log2n)
     *          * for1 - while2 的時間復雜度是：n/2 + 3n/4*3 + 7n/8 * 7，即：O(n)
     *      2. 不穩(wěn)定。相等元素分到不同組后，排序過程打亂了原本的相對位置
     * @param $data
     * @return array
     */
    public static function shellSort(&$data){
        if(!is_array($data)){
            return $data;
        }
        $data_size = count($data);
        if(0 == $data_size){
            return $data;
        }
        $gap = intval($data_size / 2);
        while($gap > 0){
            for($i=$gap; $i<$data_size; $i++){
                $temp = $data[$i];
                $ins_index = $i - $gap;
                while($ins_index >= 0 && $data[$ins_index] > $temp){
                    $data[$ins_index + $gap] = $data[$ins_index];
                    $ins_index -= $gap;
                }
                $data[$ins_index + $gap] = $temp;
            }
            $gap = intval($gap / 2);
        }
        return $data;
    }

    /**
     * 五、歸并排序
     *  思路：
     *      1. 將長度為 n 的待排序數(shù)組，分為兩個長度為 n/2 的子數(shù)組，當子數(shù)組長度為 1 時，不再二分（遞歸）
     *      2. 保證每個子數(shù)組有序后，合并成一個大數(shù)組
     *      3. 合并兩個有序的子數(shù)組成為一個有序的大數(shù)組，思路是：
     *          * 分別記錄兩個子數(shù)組的待合并元素位置
     *          * 當其中一個子數(shù)組中的元素全部合入大數(shù)組時，直接合并另外一個子數(shù)組中的元素
     *          * 當兩個子數(shù)組都還有元素未合入大數(shù)組時，取兩個子數(shù)組待合入元素中較?。ㄉ颍┗蛘咻^大（降序）排列
     * @param $data
     * @return array
     */
    public static function mergeSort(&$data){
        if(!is_array($data)){
            return $data;
        }
        $data_size = count($data);
        if(1 >= $data_size){
            return $data;
        }
        $half_size = intval($data_size / 2);
        $data_left = array_slice($data, 0, $half_size);
        $data_right = array_slice($data, $half_size, $data_size-$half_size);
        return self::merge(self::mergeSort($data_left), self::mergeSort($data_right));
    }

    private static function merge($left, $right){
        $data = [];
        $li = $ri = 0;
        for($i=0; $i<count($left)+count($right); $i++){
            if($li >= count($left)){
                $value = $right[$ri++];
            }else if($ri >= count($right)){
                $value = $left[$li++];
            }else if($left[$li] < $right[$ri]){
                $value = $left[$li++];
            }else{
                $value = $right[$ri++];
            }
            $data[$i] = $value;
        }
        return $data;
    }

    /**
     * 六、快速排序
     *  思路：
     *      1. 找到一個基準值（數(shù)組第一個元素），將所有元素分成兩組，使得左邊的元素都比基準值小，右邊的元素都比基準值大
     *      2. 以基準值的位置為分隔點，將左右兩邊的子數(shù)組進行相同操作，直到子數(shù)組的長度為 1，表示所有元素都已經(jīng)有序
     *      3. 尋找基準值得位置，且使得：基準值位置左邊的元素小于基準值，基準值位置右邊的元素大于基準值
     *          * 以第一個元素為基準值
     *          * 以第二個元素為左邊第一個元素，以最后一個元素作為右邊第一個元素
     *          * 左邊指針不斷右移，直到指針位置上的元素大于（小于）基準值
     *          * 右邊指針不斷左移，直到指針位置上的元素小于（大于）基準值
     *          * 交換左邊指針和右邊指針上的元素
     *          * 直到左邊指針和右邊指針重合，此時已經(jīng)：左邊全小于，右邊全大于
     *          * 此時的左指針或者右指針即為基準值的位置，交換第一個元素和基準值位置上的元素
     *  分析：
     *      1. 時間復雜度 O(nlog2n)，空間復雜度 O(log2n)
     *      2. 不穩(wěn)定
     *      3. 遞歸的層級是 log2n
     *      4. while - while1 - while2 - swap: 時間復雜度為 n
     * @param array $data
     * @param int $left
     * @param bool $right
     * @return array|void
     */
    public static function quickSort(&$data=[], $left=0, $right=false){
        if(!is_array($data)){
            return $data;
        }
        if(false === $right){
            $right = count($data) - 1;
        }
        if($left >= $right){
            return ;
        }
        $base = $data[$left];
        $i = $left+1;
        $j = $right;
        while(true){
            while($i <= $j && $data[$i] <= $base){
                $i++;
            }
            while($i <= $j && $data[$j] >= $base){
                $j--;
            }
            if($i >= $j){
                break;
            }
            $temp = $data[$i];
            $data[$i] = $data[$j];
            $data[$j] = $temp;
        }
        $data[$left] = $data[$j];
        $data[$j] = $base;
        self::quickSort($data, $left, $j-1);
        self::quickSort($data, $j+1, $right);
        return $data;
    }
}

$data = $data1 = $data2 = $data3 = $data4 = $data5 = $data6 = [1, 3, 5, 7, 9, 0, 2, 4, 6, 8];
echo 'data before sort: '.PHP_EOL;
print_r($data);
echo 'sorted by bubble: '.PHP_EOL;
print_r(Sort::bubbleSort($data1));
echo 'sorted by selection: '.PHP_EOL;
print_r(Sort::selectionSort($data2));
echo 'sorted by insertion: '.PHP_EOL;
print_r(Sort::insertionSort($data3));
echo 'sorted by shell: '.PHP_EOL;
print_r(Sort::shellSort($data4));
echo 'sorted by merge: '.PHP_EOL;
print_r(Sort::mergeSort($data5));
echo 'sorted by quick: '.PHP_EOL;
print_r(Sort::quickSort($data6));

php Sort.php 
data before sort: 
Array
(
    [0] => 1
    [1] => 3
    [2] => 5
    [3] => 7
    [4] => 9
    [5] => 0
    [6] => 2
    [7] => 4
    [8] => 6
    [9] => 8
)
sorted by bubble: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)
sorted by selection: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)
sorted by insertion: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)
sorted by shell: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)
sorted by merge: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)
sorted by quick: 
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)