1、冒泡排序

原理：兩兩相鄰的數(shù)進(jìn)行比較汞斧，如果反序就交換瞪浸，否則不交換
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)

<?php
function func($array) {
    $len = count($array);
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
    return $array;
}

2生真、插入排序

原理：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的數(shù)據(jù)序列的適當(dāng)位置捺宗，直到全部記錄插入完成為止柱蟀。
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)

<?php
function func(array $array)
{
    $count = count($array);
    for ($i = 1; $i < $count; $i++) { //從第二個(gè)元素開始插入
        for ($j = $i - 1; $j >= 0; $j--) { //與前面的數(shù)比較，找到插入的位置

            if ($array[$j] > $array[$j + 1]) { //比前面的數(shù)小蚜厉，交換位置
                $tmp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $tmp;
            } else { //大于或等于前面的數(shù)长已，表示已找到插入的位置
                break;
            }
        }
        echo '<pre>';print_r($array);
    }
    return $array;
}

3、選擇排序

原理：在每一次大循環(huán)的時(shí)候得出一個(gè)最大值或者最小值來替換相應(yīng)的位置
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)

function func($array) {
    $count = count($array);
    for ($i = 0; $i < $count; $i++) {
        $min = $array[$i];
        for ($j = $i + 1; $j < $count; $j++) {
            if ($array[$j] < $min) {
                $min = $array[$j];
                $array[$j] = $array[$i];
                $array[$i] = $min;
            }
        }
    }
    return $array;
}

4昼牛、快速排序

原理：通過設(shè)置一個(gè)初始中間值术瓮，來將需要排序的數(shù)組分成3部分历造，小于中間值的左邊裕膀，中間值，大于中間值的右邊闸翅，繼續(xù)遞歸用相同的方式來排序左邊和右邊伶椿，最后合并數(shù)組
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)

function func($array)
{
    if (count($array) <= 1) {
        return $array;
    }
    $middle = $array[0]; // 中間值
    $left = []; // 接收小于中間值
    $right = [];// 接收大于中間值
    // 循環(huán)比較
    for ($i = 1; $i < count($array); $i++) {
        if ($middle < $array[$i]) {
            // 大于中間值
            $right[] = $array[$i];
        } else {
            // 小于中間值
            $left[] = $array[$i];
        }
    }
    // 遞歸排序劃分好的2邊
    $left = func($left);
    $right = func($right);
    // 合并排序后的數(shù)據(jù)辜伟，別忘了合并中間值
    return array_merge($left, array($middle), $right);
}

5、歸并排序（最優(yōu)）

原理：
第一步：申請空間脊另，使其大小為兩個(gè)已經(jīng)排序序列之和导狡，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑刭送矗x擇相對小的元素放入到合并空間旱捧，并移動指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)

還有一種寫法

<?php
function mergeSort($array){
    if (count($array) <= 1) {
        return $array;
    }
    $left = array_slice($array, 0, intval(count($array)/ 2));
    $right = array_slice($array, intval(count($array)/ 2));

    $left = mergeSort($left);
    echo json_encode($left);echo "<br>";
    $right = mergeSort($right);
    echo json_encode($left);echo "<br>";

    return merge($left, $right);
}

function merge($left,$right) {
    $result = [];
    while(count($left) >0 && count($right) > 0) {
        if($left[0] <= $right[0]){
            array_push($result,array_shift($left));
        } else {
            array_push($result,array_shift($right));
        }
    }

    array_splice($result,count($result),0,$left);
    array_splice($result,count($result),0,$right);

    return $result;
}