<dialog date-time='zsw7re6t'><span draggable='oq9219'></span></dialog><span dropzone='r7rtvql'><option draggable='d5o7yt'></option></span>

          <dd date-time='2o0k7r4a'></dd>

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

          日期:2019-03-06 15:01 by 楊國偉 1079 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生成随機顔色方法彙總

          下一篇:商務通鏈接傳遞參數的擴展使用


          評論