快速排序

frank_fun 發(fā)布于2019-06-27 15:38 / 2141人閱讀

摘要：快速排序定義一個基準(zhǔn)數(shù)，用于做參照。此輪一直與的位置相遇，當(dāng)兩者相遇的時候，則將相遇位置的數(shù)與基準(zhǔn)數(shù)進行互換。左側(cè)數(shù)組為右側(cè)數(shù)組為左側(cè)數(shù)組用上述方法進行排列，變成。利用遞歸，將的數(shù)組參數(shù)左側(cè)進行判斷歸位，右側(cè)進行判斷歸位，最終返回結(jié)果。

快速排序

定義一個基準(zhǔn)數(shù)，用于做參照。

定義左右兩側(cè)的起始數(shù)和終止數(shù)，一般是以數(shù)組起始值0，以及數(shù)組長度-1為開始

數(shù)組【0】開始，與基準(zhǔn)數(shù)X進行判斷，如果比X大，則停止，保留數(shù)組【0】；比X小，則數(shù)組【0】變成數(shù)組【1】（即向右移動一位），再與基準(zhǔn)數(shù)X判斷，如此循環(huán)，到符合前面條件停止。

數(shù)組【長度-1】開始，與基準(zhǔn)數(shù)X進行判斷，如果比X小，則停止，保留數(shù)組【長度-1】；
比X大，則數(shù)組【長度-1】變成數(shù)組【長度-2】（即向左移動一位），再與基準(zhǔn)數(shù)X判斷，如此循環(huán)，到符合前面條件停止。

例如：

現(xiàn)在有數(shù)組$arr = [12, 6, 5, 35, 64, 78, 11, 85, 43,46];

我們?nèi)?b>$arr[0]=12為基準(zhǔn)數(shù)$temp。（這邊如果設(shè)置基準(zhǔn)數(shù)是最左邊的，則讓右側(cè)先開始判斷值，如果基準(zhǔn)數(shù)設(shè)置是最右邊的數(shù)，則讓左側(cè)開始先判斷）

定義變量$i=0; $j=9(數(shù)組長度-1);

然后從$arr[$j]先開始進行判斷，如果不符合條件則$j--; $j會在$arr[6]=11位置停下。

$arr[$i]開始進行判斷，如果不符合條件則$i--; $i會在$arr[3]=35位置停下。

$arr[3]與$arr[6]互換。

更換完，數(shù)組是$arr = [12, 6, 5, 11, 64, 78, 35, 85, 43,46];

更換完以后，右側(cè)的$j繼續(xù)先判斷,從$j=6開始往左走,此時$i=3。

$j此輪一直與$i=3的位置相遇，當(dāng)兩者相遇的時候，則將相遇位置($i=$j)的數(shù)與基準(zhǔn)數(shù)$temp=12進行互換。

更換完，數(shù)組是$arr = [11, 6, 5, 12, 64, 78, 35, 85, 43,46];

此時，基于$arr[3]這個位置，將數(shù)組拆分為左右兩次數(shù)組，進行相同的方式判斷（這里會用到遞歸的方法）。

左側(cè)數(shù)組為 $left_arr=[11,6,5]; 右側(cè)數(shù)組為 $right_arr=[64,78,35,85,43,46];

左側(cè)數(shù)組用上述方法進行排列，變成 $left_arr=[5,6,11];。

右側(cè)數(shù)組用上述方法進行排列，首先變成$right_arr=[43,46,35,64,85,78];

這時，左側(cè)已經(jīng)不需要排列了，因為$temp=11基準(zhǔn)數(shù)歸位后，右側(cè)沒有數(shù)組，左側(cè)5<6

右側(cè)還要進行排列,$temp=64基準(zhǔn)數(shù)歸位后，左邊數(shù)組為[43,46,35]，右邊數(shù)組[85,78]。

最終右側(cè)會變成$right_arr=[35,43,46,64,78,85];

最終數(shù)組$arr=[5,6,11,12,35,43,46,64,78,85];

代碼：

= $right) {
        return;
    }
    
    //設(shè)置基準(zhǔn)數(shù)，作為比較用的參數(shù)
    $temp = $arr[$left];

    //$i是左邊起的起始數(shù)值，$j是右邊起的起始數(shù)值
    $i = $left;
    $j = $right;

    //只要兩個參數(shù)不相等，即兩者不是指向同一個數(shù)組內(nèi)參數(shù) 則繼續(xù)循環(huán)
    while ($i != $j) {

        //從數(shù)組右側(cè)開始，判斷是否比基準(zhǔn)數(shù)小并且($j>$i)確保從右往左且還未與$i相遇
        while ($arr[$j] >= $temp && $j > $i) {
            $j--;
        }

        //從數(shù)組左側(cè)開始，判斷是否比基準(zhǔn)數(shù)大并且($j>$i)確保從左往右且還未與$j相遇
        while ($arr[$i] <= $temp && $i < $j) {
            $i++;
        }


        /**上述兩個判斷條件停止時，$i,$j都會指向數(shù)組內(nèi)的某個數(shù)$arr[$i]，$arr[$j]
         *并且$arr[$i]是比基準(zhǔn)數(shù)大的，$arr[$j]是比基準(zhǔn)數(shù)小的
         *兩者的值進行互換
         */
        if ($i < $j) {
            $t = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $t;
        }
    }
    
    
    //當(dāng)$i,$j兩個參數(shù)相等時候，則跳出循環(huán)，并且將基準(zhǔn)數(shù)與數(shù)組中（當(dāng)$j=$i的）$arr[$i]內(nèi)的值進行互換。
    $arr[$left] = $arr[$i];
    $arr[$i] = $temp;
    
    
    //利用遞歸，將$i=$j的數(shù)組參數(shù)左側(cè)進行判斷歸位，右側(cè)進行判斷歸位，最終返回結(jié)果。
    quickSort($left, $i - 1);
    quickSort($i + 1, $right);
    
    return;

}

quickSort(0, count($arr) - 1);

//輸出結(jié)果
print_r($arr);