排序算法 · 萬能Web開發文檔筆記

# 排序算法快速排序選擇一個基準元素，通常選擇第一個元素或者最后一個元素。通過一趟掃描，將待排序列分成兩部分，一部分比基準元素小，一部分大于等于基準元素。此時基準元素在其排好序后的正確位置，然后再用同樣的方法遞歸地排序劃分的兩部分。 ``` <pre class="calibre14">``` function quicksort($arr) { //判斷參數是否是一個數組 if(!is_array($arr)) return false; //遞歸出口:數組長度為1，直接返回數組 $length = count($arr); if($length<=1) return $arr; //數組元素有多個,則定義兩個空數組 $left = $right = array(); //使用for循環進行遍歷，把第一個元素當做比較的對象 for($i=1; $i<$length; $i++) { //判斷當前元素的大小 if($arr[$i]<$arr[0]){ $left[]=$arr[$i]; }else{ $right[]=$arr[$i]; } } //遞歸調用 $left=quicksort($left); $right=quicksort($right); //將所有的結果合并 return array_merge($left,array($arr[0]),$right); } ``` ``` 插入排序在要排序的一組數中，假設前面的數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。 ``` <pre class="calibre14">``` function insertsort($arr) { $len=count($arr); for($i=1; $i<$len; $i++) { //獲得當前需要比較的元素值。 $tmp = $arr[$i]; //內層循環控制比較并插入 for($j=$i-1; $j>=0; $j--) { //$arr[$i];//需要插入的元素; $arr[$j];//需要比較的元素 if($tmp < $arr[$j]) { //發現插入的元素要小，交換位置 //將后邊的元素與前面的元素互換 $arr[$j+1] = $arr[$j]; //將前面的數設置為當前需要交換的數 $arr[$j] = $tmp; } else { //如果碰到不需要移動的元素 //由于是已經排序好是數組，則前面的就不需要再次比較了。 break; } } } //將這個元素插入到已經排序好的序列內。 //返回 return $arr; } ``` ``` 選擇排序在要排序的一組數中，選出最小的一個數與第一個位置的數交換。然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。 ``` <pre class="calibre14">``` function selectsort($arr) { //$i 當前最小值的位置，需要參與比較的元素 for($i=0, $len=count($arr); $i<$len-1; $i++) { //先假設最小的值的位置 $p = $i; //$j 當前都需要和哪些元素比較，$i 后邊的。 for($j=$i+1; $j<$len; $j++) { //$arr[$p] 是當前已知的最小值 if($arr[$p] > $arr[$j]) { //比較，發現更小的,記錄下最小值的位置；并且在下次比較時，應該采用已知的最小值進行比較。 $p = $j; } } //已經確定了當前的最小值的位置，保存到$p中。 //如果發現最小值的位置與當前假設的位置$i不同，則位置互換即可 if($p != $i) { $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } } //返回最終結果 return $arr; } ``` ``` 冒泡排序在要排序的一組數中，對當前還未排好的序列，從前往后對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即，每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換 ``` <pre class="calibre14">``` function bubbleSort ($arr) { $len = count($arr); //該層循環控制需要冒泡的輪數 for ($i=1; $i<$len; $i++) { //該層循環用來控制每輪冒出一個數需要比較的次數 for ($k=0; $k<$len-$i; $k++) { if($arr[$k] > $arr[$k+1]) { $tmp = $arr[$k+1]; // 聲明一個臨時變量 $arr[$k+1] = $arr[$k]; $arr[$k] = $tmp; } } } return $arr; } ``` ``` 思路分析：希爾排序是基于插入排序的，區別在于插入排序是相鄰的一個個比較（類似于希爾中h=1的情形），而希爾排序是距離h的比較和替換。希爾排序中一個常數因子n，原數組被分成各個小組，每個小組由h個元素組成，很可能會有多余的元素。當然每次循環的時候，h也是遞減的（h=h/n）。第一次循環就是從下標為h開始。希爾排序的一個思想就是，分成小組去排序 ``` <pre class="calibre16">``` function shellsort(array $arr){ // 將$arr按升序排列 $len = count($arr); $f = 3;// 定義因子 $h = 1;// 最小為1 while ($h < $len/$f){ $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... } while ($h >= 1){ // 將數組變為h有序 for ($i = $h; $i < $len; $i++){ // 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中（算法的關鍵) for ($j = $i; $j >= $h; $j -= $h){ if ($arr[$j] < $arr[$j-$h]){ $temp = $arr[$j]; $arr[$j] = $arr[$j-$h]; $arr[$j-$h] = $temp; } //print_r($arr);echo ' '; // 打開這行注釋，可以看到每一步被替換的情形 } } $h = intval($h/$f); } return $arr; } ``` ```