首頁 >後端開發 >php教程 >php快速排序原理與實作方法及實例分析

php快速排序原理與實作方法及實例分析

墨辰丷原創: 2018-06-02 10:00:021394瀏覽

這篇文章主要介紹了php快速排序原理與實現方法,結合實例形式分析了php快速排序的演算法原理與具體實現技巧,需要的朋友可以參考下

具體如下：

<?php
$n = array(&#39;13&#39;,&#39;14&#39;,&#39;55&#39;,&#39;10&#39;,&#39;54&#39;,&#39;2&#39;,&#39;79&#39;,&#39;106&#39;,&#39;89&#39;,&#39;90&#39;,&#39;22&#39;,&#39;60&#39;,&#39;111&#39;,&#39;77777&#39;,&#39;-110&#39;,&#39;-10&#39;,&#39;123&#39;);
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

快速排序是對冒泡排序的一種改進。它的基本想法是：透過一躺排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一不部分的所有資料都要小，然後再按次方法對這兩部分資料分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

假設要排序的陣列是A[1]…A[N]，首先任意選取一個資料（通常選用第一個資料）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1）、設定兩個變數I、J，排序開始的時候I：=1，J：=N；
2）、以第一個陣列元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即從後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；
4）、從I開始向後搜索，即由前開始向後搜索（I：=I 1），找到第一個大於X的值，兩者交換；
5）、重複第3、4步，直到I=J；

快速排序就是遞歸呼叫此過程－在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列

總結：以上就是本篇的全部內容，希望能對大家的學習有所幫助。

php快速排序原理與實作方法及實例分析

相關文章