文章熱詞:php快速排序,php冒泡排序,

            日期:2019-03-06 15:01 by admin 1205 0 收藏
            我要分享

            摘要:其實快速排序之所以稱之快速,就是因爲,冒泡排序是每次對比隻交換相鄰的兩個值的位置,這樣每個值要移動到它最終的排序結果中所對應的位置,可能需要很多次位置的變化。

            其實快速排序之所以稱之快速,就是因爲,冒泡排序是每次對比隻交換相鄰的兩個值的位置,這樣每個值要移動到它最終的排序結果中所對應的位置,可能需要很多次位置的變化。

            這裏先借用百度的一張圖來看一下,比較形象:

            a0f46208bb45993f7608cc811714ca31.gif

            概念:

            快速排序算法是對冒泡算法的一個優化。他的思想是先對數組進行分割, 把大的元素數值放到一個臨時數組裏,把小的元素數值放到另一個臨時數組裏(這個分割的點可以是數組中的任意一個元素值,一般用第一個元素,即$array[0]),然後繼續把這兩個臨時數組重複上面拆分,最後把小的數組元素和大的數組元素合并起來。這裏用到了遞歸的思想。

            PHP代碼:

            function quickSort($array)
            {
                if(!isset($array[1]))
                    return $array;
                $mid = $array[0]; //獲取一個用于分割的關鍵字,一般是首個元素
                $leftArray = array(); 
                $rightArray = array();
                foreach($array as $v)
                {
                    if($v > $mid)
                        $rightArray[] = $v;  //把比$mid大的數放到一個數組裏
                    if($v < $mid)
                        $leftArray[] = $v;   //把比$mid小的數放到另一個數組裏
                }
                $leftArray = quickSort($leftArray); //把比較小的數組再一次進行分割
                $leftArray[] = $mid;        //把分割的元素加到小的數組後面,不能忘了它哦
                $rightArray = quickSort($rightArray);  //把比較大的數組再一次進行分割
                return array_merge($leftArray,$rightArray);  //組合兩個結果
            }


            與冒泡算法對比

            這裏我與之前寫的冒泡算法實現的排序做了個對比,可以看出這個算法比冒泡算法的效率要高很多。

            $a = array_rand(range(1,3000), 1500);  //甚至在冒泡算法超過1600個元素的時候會出現内存不足的提示,但這裏爲了測出兩個之間的差别大小, 就設置成了1500,保證冒泡算法也能執行完畢。
            shuffle($a);  //獲取已經打亂了順序的數組
            $t1 = microtime(true);
            quickSort($a);  //快速排序
            $t2 = microtime(true);
            echo (($t2-$t1)*1000).'ms<br/>';
            require('./maopao.php');  //這裏引用的是我之前寫的冒泡算法排序
            $t1 = microtime(true);
            maoPao($a);   //冒泡
            $t2 = microtime(true);
            echo (($t2-$t1)*1000).'ms';

            運行結果:

            12.10880279541ms
            772.64094352722ms

            從結果可以看出,快速排序算法比普通的冒泡要高效的多。


            上一篇:php生成随機顔色方法彙總

            下一篇:HTTP協議三次握手過程詳解


            評論

            -->