摘要：良好的排序算法具有進(jìn)行最少的比較和交換的特征。冒泡排序是一個(gè)基于比較的排序算法，被認(rèn)為是效率最低的排序算法之一。現(xiàn)在讓我們使用實(shí)現(xiàn)冒泡排序算法。插入排序到目前為止，我們已經(jīng)看到了兩種基于比較的排序算法。

本文適合對于排序算法不太了解的新手同學(xué)觀看，大佬直接忽略即可。因?yàn)榭紤]到連貫性，所以篇幅較長。老鐵們看完需要大概一個(gè)小時(shí)，但是從入門到完全理解可能需要10個(gè)小時(shí)(哈哈哈，以我自己的經(jīng)歷來計(jì)算的)，所以各位老鐵可以先收藏下來，同步更新在Github，本文引用到的所有算法的實(shí)現(xiàn)在這個(gè)地址，每天抽點(diǎn)時(shí)間理解一個(gè)排序算法即可。

我們的數(shù)據(jù)大多數(shù)情況下是未排序的，這意味著我們需要一種方法來進(jìn)行排序。我們通過將不同元素相互比較并提高一個(gè)元素的排名來完成排序。在大多數(shù)情況下，如果沒有比較，我們就無法決定需要排序的部分。在比較之后，我們還需要交換元素，以便我們可以對它們進(jìn)行重新排序。良好的排序算法具有進(jìn)行最少的比較和交換的特征。除此之外，還存在基于非比較的排序，這類排序不需要比較數(shù)據(jù)來進(jìn)行排序。我們將在這篇文章中為各位老鐵介紹這些算法。以下是本篇文章中我們將要討論的一些排序算法：

Bubble sort

Insertion sort

Selection sort

Quick sort

Merge sort

Bucket sort

以上的排序可以根據(jù)不同的標(biāo)準(zhǔn)進(jìn)行分組和分類。例如簡單排序，高效排序，分發(fā)排序等。我們現(xiàn)在將探討每個(gè)排序的實(shí)現(xiàn)和復(fù)雜性分析，以及它們的優(yōu)缺點(diǎn)。

我們先看下本文提到的各類排序算法的時(shí)間空間復(fù)雜度以及穩(wěn)定性。各位老鐵可以點(diǎn)擊這里了解更多。

冒泡排序是編程世界中最常討論的一個(gè)排序算法，大多數(shù)開發(fā)人員學(xué)習(xí)排序的第一個(gè)算法。冒泡排序是一個(gè)基于比較的排序算法，被認(rèn)為是效率最低的排序算法之一。冒泡排序總是需要最大的比較次數(shù)，平均復(fù)雜度和最壞復(fù)雜度都是一樣的。

冒泡排序中，每一個(gè)待排的項(xiàng)目都會(huì)和剩下的項(xiàng)目做比較，并且在需要的時(shí)候進(jìn)行交換。下面是冒泡排序的偽代碼。

procedure bubbleSort(A: list of sortable items)
n = length(A)
for i = 0 to n inclusive do
 for j = 0 to n - 1 inclusive do
    if A[j] > A[j + 1] then
        swap(A[j + 1], A[j])
    end if
  end for
end for
end procedure

正如我們從前面的偽代碼中看到的那樣，我們首先運(yùn)行一個(gè)外循環(huán)以確保我們迭代每個(gè)數(shù)字，內(nèi)循環(huán)確保一旦我們指向某個(gè)項(xiàng)目，我們就會(huì)將該數(shù)字與數(shù)據(jù)集合中的其他項(xiàng)目進(jìn)行比較。下圖顯示了對列表中的一個(gè)項(xiàng)目進(jìn)行排序的單次迭代。假設(shè)我們的數(shù)據(jù)包含以下項(xiàng)目：20,45,93,67,10,97,52,88,33,92。第一次迭代將會(huì)是以下步驟：

有背景顏色的項(xiàng)目顯示的是我們正在比較的兩個(gè)項(xiàng)目。我們可以看到，外部循環(huán)的第一次迭代導(dǎo)致最大的項(xiàng)目存儲(chǔ)在列表的最頂層位置。然后繼續(xù)，直到我們遍歷列表中的每個(gè)項(xiàng)目。現(xiàn)在讓我們使用PHP實(shí)現(xiàn)冒泡排序算法。

我們可以使用PHP數(shù)組來表示未排序的數(shù)字列表。由于數(shù)組同時(shí)具有索引和值，我們根據(jù)位置輕松迭代每個(gè)項(xiàng)目，并將它們交換到合適的位置。

function bubbleSort(&$arr) : void
{
    $swapped = false;
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        for ($j = 0; $j < $c - 1; $j ++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
            }
        }
    }
}

對于第一遍，在最壞的情況下，我們必須進(jìn)行n-1比較和交換。 對于第2次遍歷，在最壞的情況下，我們需要n-2比較和交換。 所以，如果我們一步一步地寫它，那么我們將看到：復(fù)雜度= n-1 + n-2 + ..... + 2 + 1 = n *（n-1）/ 2 = O(n2)。因此，冒泡排序的復(fù)雜性是O(n2)。 分配臨時(shí)變量，交換，遍歷內(nèi)部循環(huán)等需要一些恒定的時(shí)間，但是我們可以忽略它們，因?yàn)樗鼈兪遣蛔兊摹Ｒ韵率敲芭菖判虻臅r(shí)間復(fù)雜度表，適用于最佳，平均和最差情況：

盡管冒泡排序的時(shí)間復(fù)雜度是O(n2)，但是我們可以使用一些改進(jìn)的手段來減少排序過程中對數(shù)據(jù)的比較和交換次數(shù)。最好的時(shí)間復(fù)雜度是O(n)是因?yàn)槲覀冎辽僖淮蝺?nèi)部循環(huán)才可以確定數(shù)據(jù)已經(jīng)是排好序的狀態(tài)。

冒泡排序最重要的一個(gè)方面是，對于外循環(huán)中的每次迭代，都會(huì)有至少一次交換。如果沒有交換，則列表已經(jīng)排序。我們可以利用它改進(jìn)我們的偽代碼

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        swapped = false
        for j = i to n - 1 inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
            endif
        end for
        if swapped = false
            break
        endif
    end for
end procedure
    

正如我們所看到的，我們現(xiàn)在為每個(gè)迭代設(shè)置了一個(gè)標(biāo)志為false，我們期望在內(nèi)部迭代中，標(biāo)志將被設(shè)置為true。如果內(nèi)循環(huán)完成后標(biāo)志仍然為假，那么我們可以打破外循環(huán)。

function bubbleSort(&$arr) : void
{
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        $swapped = false;
        for ($j = 0; $j < $c - 1; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
            }
        }

        if (!$swapped) break; //沒有發(fā)生交換，算法結(jié)束
    }
}

我們還發(fā)現(xiàn)，在第一次迭代中，最大項(xiàng)放置在數(shù)組的右側(cè)。在第二個(gè)循環(huán)，第二大的項(xiàng)將位于數(shù)組右側(cè)的第二個(gè)。我們可以想象出來在每次迭代之后，第i個(gè)單元已經(jīng)存儲(chǔ)了已排序的項(xiàng)目，不需要訪問該索引和
做比較。因此，我們可以從內(nèi)部迭代減少迭代次數(shù)并減少比較。這是我們的第二個(gè)改進(jìn)的偽代碼

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        swapped = false
        for j = 1 to n - i - 1 inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
            endif
        end for
        if swapped = false
            break
        end if
    end for
end procedure
   

下面的是PHP的實(shí)現(xiàn)

function bubbleSort(&$arr) : void
{
    
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        $swapped = false;
        for ($j = 0; $j < $c - $i - 1; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
            }

            if (!$swapped) break; //沒有發(fā)生交換，算法結(jié)束
        }
    }
}

我們查看代碼中的內(nèi)循環(huán)，唯一的區(qū)別是$j < $c - $i - 1；其他部分與第一次改進(jìn)一樣。因此，對于20、45、93、67、10、97、52、88、33、92, 我們可以很認(rèn)為，在第一次迭代之后，頂部數(shù)字97將不被考慮用于第二次迭代比較。同樣的情況也適用于93，將不會(huì)被考慮用于第三次迭代。

我們看看前面的圖，腦海中應(yīng)該馬上想到的問題是“92不是已經(jīng)排序了嗎？我們是否需要再次比較所有的數(shù)字？是的，這是一個(gè)好的問題。我們完成了內(nèi)循環(huán)中的最后一次交換后可以知道在哪一個(gè)位置，之后的數(shù)組已經(jīng)被排序。因此，我們可以為下一個(gè)循環(huán)設(shè)置一個(gè)界限，偽代碼是這樣的：

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    bound = n - 1
    for i = 1 to n inclusive do
        swapped = false
        bound = 0
        for j = 1 to bound inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
                newbound = j
            end if
        end for
        bound = newbound
        if swapped = false
            break
        endif
    end for
end procedure
   

這里，我們在每個(gè)內(nèi)循環(huán)完成之后設(shè)定邊界，并且確保我們沒有不必要的迭代。下面是PHP代碼：

function bubbleSort(&$arr) : void
{
    $swapped = false;
    $bound = count($arr) - 1;
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        for ($j = 0; $j < $bound; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
                $newBound = $j;
            }
        }
        $bound = $newBound;
        if (!$swapped) break; //沒有發(fā)生交換，算法結(jié)束
    }
}

選擇排序是另一種基于比較的排序算法，它類似于冒泡排序。最大的區(qū)別是它比冒泡排序需要更少的交換。在選擇排序中，我們首先找到數(shù)組的最小/最大項(xiàng)并將其放在第一位。如果我們按降序排序，那么我們將從數(shù)組中獲取的是最大值。對于升序，我們獲取的是最小值。在第二次迭代中，我們將找到數(shù)組的第二個(gè)最大值或最小值，并將其放在第二位。持續(xù)到我們把每個(gè)數(shù)字放在正確的位置。這就是所謂的選擇排序，選擇排序的偽代碼如下：

procedure  selectionSort( A : list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        min  =  i
        for j = i + 1 to n inclusive do
            if  A[j] < A[min] then
                min = j 
            end if
        end  for

        if min != i
            swap(a[i], a[min])
        end if
    end  for
end procedure

看上面的算法，我們可以發(fā)現(xiàn)，在外部循環(huán)中的第一次迭代之后，第一個(gè)最小項(xiàng)被存儲(chǔ)在第一個(gè)位置。在第一次迭代中，我們選擇第一個(gè)項(xiàng)目，然后從剩下的項(xiàng)目（從2到n）找到最小值。我們假設(shè)第一個(gè)項(xiàng)目是最小值。我們找到另一個(gè)最小值，我們將標(biāo)記它的位置，直到我們掃描了剩余的列表并找到新的最小最小值。如果沒有找到最小值，那么我們的假設(shè)是正確的，這確實(shí)是最小值。如下圖：

正如我們在前面的圖中看到的，我們從列表中的第一個(gè)項(xiàng)目開始。然后，我們從數(shù)組的其余部分中找到最小值10。在第一次迭代結(jié)束時(shí)，我們只交換了兩個(gè)地方的值（用箭頭標(biāo)記）。因此，在第一次迭代結(jié)束時(shí)，我們得到了的數(shù)組中得到最小值。然后，我們指向下一個(gè)數(shù)字45，并開始從其位置的右側(cè)找到下一個(gè)最小的項(xiàng)目，我們從剩下的項(xiàng)目中找到了20（如兩個(gè)箭頭所示）。在第二次迭代結(jié)束時(shí)，我們將第二個(gè)位置的值和從列表的剩余部分新找到的最小位置交換。這個(gè)操作一直持續(xù)到最后一個(gè)元素，在過程結(jié)束時(shí)，我們得到了一個(gè)排序的列表，下面是PHP代碼的實(shí)現(xiàn)。

function selectionSort(&$arr)
{
    $count = count($arr);

    //重復(fù)元素個(gè)數(shù)-1次
    for ($j = 0; $j <= $count - 1; $j++) {
        //把第一個(gè)沒有排過序的元素設(shè)置為最小值
        $min = $arr[$j];
        //遍歷每一個(gè)沒有排過序的元素
        for ($i = $j + 1; $i < $count; $i++) {
            //如果這個(gè)值小于最小值
            if ($arr[$i] < $min) {
                //把這個(gè)元素設(shè)置為最小值
                $min = $arr[$i];
                //把最小值的位置設(shè)置為這個(gè)元素的位置
                $minPos = $i;
            }
        }
        //內(nèi)循環(huán)結(jié)束把最小值和沒有排過序的元素交換
        list($arr[$j], $arr[$minPos]) = [$min, $arr[$j]];
    }
    
}

選擇排序看起來也類似于冒泡排序，它有兩個(gè)for循環(huán)，從0到n。冒泡排序和選擇排序的區(qū)別在于，在最壞的情況下，選擇排序使交換次數(shù)達(dá)到最大n - 1，而冒泡排序可以需要 n * n 次交換。在選擇排序中，最佳情況、最壞情況和平均情況具有相似的時(shí)間復(fù)雜度。

到目前為止，我們已經(jīng)看到了兩種基于比較的排序算法。現(xiàn)在，我們將探索另一個(gè)排序算法——插入排序。與剛才看到的其他兩個(gè)排序算法相比，它有最簡單的實(shí)現(xiàn)。如果項(xiàng)目的數(shù)量較小，插入排序優(yōu)于冒泡排序和選擇排序。如果數(shù)據(jù)集很大，就像冒泡排序一樣就變得效率低下。插入排序的工作原理是將數(shù)字插入到已排序列表的正確位置。它從數(shù)組的第二項(xiàng)開始，并判斷該項(xiàng)是否小于當(dāng)前值。如果是這樣，它將項(xiàng)目轉(zhuǎn)移，并將較小的項(xiàng)目存儲(chǔ)在其正確的位置。然后，它移動(dòng)到下一項(xiàng)，并且相同的原理繼續(xù)下去，直到整個(gè)數(shù)組被排序。

procedure insertionSort(A: list of sortable items)
    n length(A)
    for i=1 to n inclusive do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j+1] = A[j]
            j--
        end while
        A[j + 1] = key
    end for
end procedure

假如我們有下列數(shù)組，元素是：20 45 93 67 10 97 52 88 33 92。我們從第二個(gè)項(xiàng)目45開始?，F(xiàn)在我們將從45的左邊第一個(gè)項(xiàng)目開始，然后到數(shù)組的開頭，看看左邊是否有大于45的值。由于只有20，所以不需要插入，目前兩項(xiàng)(20, 45)被排序?，F(xiàn)在我們將指針移到93，從它再次開始，比較從45開始，由于45不大于93，我們停止?，F(xiàn)在，前三項(xiàng)（20, 45, 93）已排序。接下來，對于67，我們從數(shù)字的左邊開始比較。左邊的第一個(gè)數(shù)字是93，它較大，所以必須移動(dòng)一個(gè)位置。我們移動(dòng)93到67的位置。然后，我們移動(dòng)到它左邊的下一個(gè)項(xiàng)目45。45小于67，不需要進(jìn)一步的比較?，F(xiàn)在，我們先將93移動(dòng)到67的位置，然后我們插入67的到93的位置。繼續(xù)如上操作直到整個(gè)數(shù)組被排序。下圖說明在每個(gè)步驟中使用插入排序的直到完全排序過程。

function insertionSort(array &$arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

插入排序具有與冒泡排序相似的時(shí)間復(fù)雜度。與冒泡排序的區(qū)別是交換的數(shù)量遠(yuǎn)低于冒泡排序。

到目前為止，我們已經(jīng)了解了每次對完整列表進(jìn)行排序的一些排序算法。我們每次都需要應(yīng)對一個(gè)比較大的數(shù)字集合。我們可以設(shè)法使數(shù)據(jù)集合更小，從而解決這個(gè)問題。分治思想對我們有很大幫助。用這種方法，我們將一個(gè)問題分成兩個(gè)或多個(gè)子問題或集合，然后在組合子問題的所有結(jié)果以獲得最終結(jié)果。這就是所謂的分而治之方法，分而治之方法可以讓我們有效地解決排序問題，并降低算法的復(fù)雜度。最流行的兩種排序算法是合并排序和快速排序，它們應(yīng)用分治算法對數(shù)據(jù)進(jìn)行排序，因此被認(rèn)為是最好的排序算法。

正如我們已經(jīng)知道的，歸并排序應(yīng)用分治方法來解決排序問題，我們用法兩個(gè)過程來解決這個(gè)問題。第一個(gè)是將問題集劃分為足夠小的問題，以便容易地求解，然后將這些結(jié)果結(jié)合起來。我們將用遞歸方法來完成分治部分。下面的圖顯示了如何采用分治的方法。

基于前面的圖像，我們現(xiàn)在可以開始準(zhǔn)備我們的代碼，它將有兩個(gè)部分。

/**
 * 歸并排序
 * 核心：兩個(gè)有序子序列的歸并(function merge)
 * 時(shí)間復(fù)雜度任何情況下都是 O(nlogn)
 * 空間復(fù)雜度 O(n)
 * 發(fā)明人: 約翰·馮·諾伊曼
 * 速度僅次于快速排序，為穩(wěn)定排序算法，一般用于對總體無序，但是各子項(xiàng)相對有序的數(shù)列
 * 一般不用于內(nèi)(內(nèi)存)排序，一般用于外排序
 */

function mergeSort($arr)
{
    $lenght = count($arr); 
    if ($lenght == 1) return $arr;
    $mid = (int)($lenght / 2);

    //把待排序數(shù)組分割成兩半
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return merge($left, $right);
}

function merge(array $left, array $right)
{
    //初始化兩個(gè)指針
    $leftIndex = $rightIndex = 0;
    $leftLength = count($left);
    $rightLength = count($right);
    //臨時(shí)空間
    $combine = [];

    //比較兩個(gè)指針?biāo)诘脑?    while ($leftIndex < $leftLength && $rightIndex < $rightLength) {
        //如果左邊的元素大于右邊的元素，就將右邊的元素放在多帶帶的數(shù)組，并將右指針向后移動(dòng)
        if ($left[$leftIndex] > $right[$rightIndex]) {
            $combine[] = $right[$rightIndex];
            $rightIndex++;
        } else {
            //如果右邊的元素大于左邊的元素，就將左邊的元素放在多帶帶的數(shù)組，并將左指針向后移動(dòng)
            $combine[] = $left[$leftIndex];
            $leftIndex++;
        }
    }

    //右邊的數(shù)組全部都放入到了返回的數(shù)組，然后把左邊數(shù)組的值放入返回的數(shù)組
    while ($leftIndex < $leftLength) {
        $combine[] = $left[$leftIndex];
        $leftIndex++;
    }

    //左邊的數(shù)組全部都放入到了返回的數(shù)組，然后把右邊數(shù)組的值放入返回的數(shù)組
    while ($rightIndex < $rightLength) {
        $combine[] = $right[$rightIndex];
        $rightIndex++;
    }

    return $combine;
}

我們劃分?jǐn)?shù)組，直到它達(dá)到1的大小。然后，我們開始使用合并函數(shù)合并結(jié)果。在合并函數(shù)中，我們有一個(gè)數(shù)組來存儲(chǔ)合并的結(jié)果。正因?yàn)槿绱?，合并排序?qū)嶋H上比我們迄今所看到的其他算法具有更大的空間復(fù)雜度。

由于歸并排序遵循分而治之的方法，所以我們必須解決這兩個(gè)復(fù)雜問題。對于n個(gè)大小的數(shù)組，我們首先需要將數(shù)組分成兩個(gè)部分，然后合并它們以得到n個(gè)大小的數(shù)組。我們可以看下面的示意圖

解決每一層子問題需要的時(shí)間都是cn，假設(shè)一共有l(wèi)層，那么總的時(shí)間復(fù)雜度會(huì)是ln。因?yàn)橐还灿衛(wèi)ogn + 1
層，那么結(jié)果就是 cn(logn + 1)。我們刪除常數(shù)階和線性階，最后的結(jié)果可以得出時(shí)間復(fù)雜度就是O(nlog2n)。

快速排序是對冒泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

function qSort(array &$arr, int $p, int $r)
{
    if ($p < $r) {
        $q = partition($arr, $p, $r);
        qSort($arr, $p, $q);
        qSort($arr, $q + 1, $r);
    }
}

function partition(array &$arr, int $p, int $r)
{
    $pivot = $arr[$p];
    $i = $p - 1;
    $j = $r + 1;

    while (true) {
        do {
            $i++;
        } while ($arr[$i] < $pivot);

        do {
            $j--;
        } while ($arr[$j] > $pivot);

        if ($i < $j) {
            list($arr[$i], $arr[$j]) = [$arr[$j], $arr[$i]];
        } else {
            return $j;
        }

    }
}

最壞情況下快速排序具有與冒泡排序相同的時(shí)間復(fù)雜度，pivot的選取非常重要。下面是快速排序的復(fù)雜度分析。

對于快速排序的優(yōu)化，有興趣的老鐵可以點(diǎn)擊這里查看。

桶排序 (Bucket sort)或所謂的箱排序，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。

/**
 * 桶排序
 * 不是一種基于比較的排序
 * T(N, M) = O(M + N) N是帶排序的數(shù)據(jù)的個(gè)數(shù)，M是數(shù)據(jù)值的數(shù)量
 * 當(dāng) M >> N 時(shí)，需要考慮使用基數(shù)排序
 */

function bucketSort(array &$data)
{
    $bucketLen = max($data) - min($data) + 1;
    $bucket = array_fill(0, $bucketLen, []);

    for ($i = 0; $i < count($data); $i++) {
        array_push($bucket[$data[$i] - min($data)], $data[$i]);
    }

    $k = 0;

    for ($i = 0; $i < $bucketLen; $i++) {
        $currentBucketLen = count($bucket[$i]);

        for ($j = 0; $j < $currentBucketLen; $j++) {
            $data[$k] = $bucket[$i][$j];
            $k++;
        }
    }
}

基數(shù)排序的PHP實(shí)現(xiàn)，有興趣的同學(xué)同樣可以訪問這個(gè)頁面來查看。

桶排序的時(shí)間復(fù)雜度優(yōu)于其他基于比較的排序算法。以下是桶排序的復(fù)雜性

PHP有豐富的預(yù)定義函數(shù)庫，也包含不同的排序函數(shù)。它有不同的功能來排序數(shù)組中的項(xiàng)目，你可以選擇按值還是按鍵/索引進(jìn)行排序。在排序時(shí)，我們還可以保持?jǐn)?shù)組值與它們各自的鍵的關(guān)聯(lián)。下面是這些函數(shù)的總結(jié)

對于sort()、rsort()、ksort()、krsort()、asort()以及 arsort()下面的常量可以使用

SORT_REGULAR - 正常比較單元（不改變類型）

SORT_NUMERIC - 單元被作為數(shù)字來比較

SORT_STRING - 單元被作為字符串來比較

SORT_LOCALE_STRING - 根據(jù)當(dāng)前的區(qū)域（locale）設(shè)置來把單元當(dāng)作字符串比較，可以用 setlocale() 來改變。

SORT_NATURAL - 和 natsort() 類似對每個(gè)單元以“自然的順序”對字符串進(jìn)行排序。 PHP 5.4.0 中新增的。

SORT_FLAG_CASE - 能夠與 SORT_STRING 或 SORT_NATURAL 合并（OR 位運(yùn)算），不區(qū)分大小寫排序字符串。

本文引用到的所有算法的實(shí)現(xiàn)在這個(gè)地址，主要內(nèi)容是使用PHP語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。歡迎各位老鐵收藏～