當前位置:首頁 > PHP教程 > php應用 > 列表

7種php基本排序實現方法

發布:smiling 來源: PHP粉絲網  添加日期:2019-11-18 18:11:43 瀏覽: 評論:0 

本文總結了一下常用的7種排序方法,并用php語言實現。

1、直接插入排序

  1. /* 
  2.  
  3.  *  直接插入排序,插入排序的思想是:當前插入位置之前的元素有序, 
  4.  
  5.  *  若插入當前位置的元素比有序元素最后一個元素大,則什么也不做, 
  6.  
  7.  *  否則在有序序列中找到插入的位置,并插入 
  8.  
  9.  */ 
  10.  
  11. function insertSort($arr) { 
  12.  
  13.   $len = count($arr);   
  14.  
  15.   for($i = 1; $i < $len$i++) { 
  16.  
  17.     if($arr[$i-1] > $arr[i]) { 
  18.  
  19.       for($j = $i - 1;$j >= 0; $j-- ) { 
  20.  
  21.         $tmp = $arr[$j+1]; 
  22.  
  23.         if($tmp < $arr[$j]) { 
  24.  
  25.           $arr[$j+1] = $arr[$j]; 
  26.  
  27.           $arr[$j] = $tmp
  28.  
  29.         }else
  30.  
  31.           break
  32.  
  33.         }           
  34. //phpfensi.com 
  35.       }   
  36.  
  37.     } 
  38.  
  39.   }   
  40.  
  41.   return $arr
  42.  

2、冒泡排序

  1. /* 
  2.  
  3.   冒泡排序,冒泡排序思想:進行 n-1 趟冒泡排序, 每趟兩兩比較調整最大值到數組(子數組)末尾 
  4.  
  5. */ 
  6.  
  7. function bubbleSort($arr) { 
  8.  
  9.   $len = count($arr); 
  10.  
  11.   for($i = 1; $i < $len$i++) { 
  12.  
  13.     for($j = 0; $j < $len-$i$j++) { 
  14.  
  15.       if($arr[$j] > $arr[$j+1]) { 
  16.  
  17.         $tmp = $arr[$j+1]; 
  18.  
  19.         $arr[$j+1] = $arr[$j]; 
  20.  
  21.         $arr[$j] = $tmp
  22.  
  23.       } 
  24.  
  25.     } 
  26.  
  27.   } 
  28.  
  29.   return $arr
  30.  

3、簡單選擇排序

  1. /* 
  2.  
  3.   簡單選擇排序, 簡單排序思想:從數組第一個元素開始依次確定從小到大的元素 
  4.  
  5. */ 
  6.  
  7. function selectSort($arr) { 
  8.  
  9.   $len = count($arr); 
  10.  
  11.   for($i = 0; $i < $len$i++) { 
  12.  
  13.     $k = $i
  14.  
  15.     for($j = $i+1; $j < $len$j++) { 
  16.  
  17.       if($arr[$k] > $arr[$j]) { 
  18.  
  19.         $k = $j
  20.  
  21.       } 
  22.  
  23.     } 
  24.  
  25.     if($k != $i) { 
  26.  
  27.       $tmp = $arr[$i]; 
  28.  
  29.       $arr[$i] = $arr[$k]; 
  30.  
  31.       $arr[$k] = $tmp
  32. //phpfensi.com 
  33.     } 
  34.  
  35.   } 
  36.  
  37.   return $arr
  38.  

4、希爾排序

  1. /* 
  2.  
  3.   希爾排序,希爾排序原理:將數組按指定步長分隔成若干子序列,然后分別對子序列進行排序(在這是直接) 
  4.  
  5. */ 
  6.  
  7. function shellSort($arr) { 
  8.  
  9.   $len = count($arr); 
  10.  
  11.   $k = floor($len/2); 
  12.  
  13.   while($k > 0) { 
  14.  
  15.     for($i = 0; $i < $k$i++) { 
  16.  
  17.       for($j = $i$j < $len, ($j + $k) < $len$j = $j + $k) { 
  18.  
  19.         if($arr[$j] > $arr[$j+$k]) { 
  20.  
  21.           $tmp = $arr[$j+$k]; 
  22.  
  23.           $arr[$j+$k] = $arr[$j]; 
  24.  
  25.           $arr[$j] = $tmp
  26.  
  27.         } 
  28. //phpfensi.com 
  29.       } 
  30.  
  31.     } 
  32.  
  33.     $k = floor($k/2); 
  34.  
  35.   } 
  36.  
  37.   return $arr
  38.  

5、快速排序

  1. /* 
  2.  
  3.  *  快速排序,快排思想:通過一趟排序將待排的記錄分為兩個獨立的部分,其中一部分的記錄的關鍵字均不大于 
  4.  
  5.  *  另一部分記錄的關鍵字,然后再分別對這兩部分記錄繼續進行快速排序,以達到整個序列有序,具體做法需要 
  6.  
  7.  *  每趟排序設置一個標準關鍵字和分別指向頭一個記錄的關鍵字和最后一個記錄的關鍵字的指針。 
  8.  
  9.  *  quickSort($arr, 0, count($arr) -1); 
  10.  
  11.  */ 
  12.  
  13. function quickSort(&$arr,$low,$high) { 
  14.  
  15.   if($low < $high) { 
  16.  
  17.     $i = $low
  18.  
  19.     $j = $high
  20.  
  21.     $primary = $arr[$low]; 
  22.  
  23.     while($i < $j) { 
  24.  
  25.       while($i < $j && $arr[$j] >= $primary) { 
  26.  
  27.         $j--; 
  28.  
  29.       } 
  30.  
  31.       if($i < $j) { 
  32.  
  33.         $arr[$i++] = $arr[$j]; 
  34.  
  35.       } 
  36.  
  37.       while($i < $j && $arr[$i] <= $primary) { 
  38.  
  39.         $i++; 
  40.  
  41.       } 
  42.  
  43.       if($i < $j) { 
  44.  
  45.         $arr[$j--] = $arr[$i]; 
  46.  
  47.       } 
  48.  
  49.     } 
  50.  
  51.     $arr[$i] = $primary
  52.  
  53.     quickSort($arr$low$i-1); 
  54.  
  55.     quickSort($arr$i+1, $high); 
  56.  
  57.   } 
  58.  

6、堆排序

  1. /* 
  2.   堆排序 
  3.  
  4. */ 
  5.  
  6. // 調整子堆的為大根堆的過程,$s為子堆的根的位置,$m為堆最后一個元素位置 
  7.  
  8. function heapAdjust(&$arr$s$m) { 
  9.  
  10.   $tmp = $arr[$s]; 
  11.  
  12.   // 在調整為大根堆的過程中可能會影響左子堆或右子堆 
  13.  
  14.   // for循環的作用是要保證子堆也是大根堆 
  15.  
  16.   for($j = 2*$s + 1; $j <= $m$j = 2*$j + 1) { 
  17.  
  18.     // 找到根節點的左右孩子中的最大者,然后用這個最大者與根節點比較, 
  19.  
  20.     // 若大則進行調整,否則符合大根堆的 特點跳出循環   
  21.  
  22.     if($j < $m && $arr[$j] < $arr[$j+1]) { 
  23.  
  24.       $j++; 
  25.  
  26.     } 
  27.  
  28.     if($tmp >= $arr[$j] ) { 
  29.  
  30.       break
  31.  
  32.     } 
  33.  
  34.     $arr[$s] = $arr[$j]; 
  35.  
  36.     $s = $j
  37.  
  38.   } 
  39.  
  40.   $arr[$s] = $tmp
  41.  
  42. //phpfensi.com 
  43.  
  44. // 堆排序 
  45.  
  46. function heapSort($arr) { 
  47.  
  48.   $len = count($arr); 
  49.  
  50.   // 依次從子堆開始調整堆為大根堆 
  51.  
  52.   for($i = floor($len/2-1); $i >= 0; $i--) { 
  53.  
  54.     heapAdjust($arr$i$len-1); 
  55.  
  56.   } 
  57.  
  58.   // 依次把根節點調換至最后一個位置,再次調整堆為大根堆,找到次最大值, 
  59.  
  60.   // 依次類推得到一個有序數組 
  61.  
  62.   for($n = $len-1; $n > 0; $n--) { 
  63.  
  64.     $tmp = $arr[$n]; 
  65.  
  66.     $arr[$n] = $arr[0]; 
  67.  
  68.     $arr[0] = $tmp
  69.  
  70.     heapAdjust($arr, 0, $n-1); 
  71.  
  72.   } 
  73.  
  74.   return $arr
  75.  

7、歸并排序

  1. /* 
  2.  
  3.   歸并排序,這里實現的是兩路歸并 
  4.  
  5. */ 
  6.  
  7. // 分別將有序的$arr1[s..m]、$arr2[m+1..n]歸并為有序的$arr2[s..n] 
  8.  
  9. function Merge(&$arr1, &$arr2$s$m$n) { 
  10.  
  11.   for($k = $s,$i = $s$j = $m+1; $i <= $m && $j <= $n$k++) { 
  12.  
  13.     if($arr1[$i]<$arr1[$j]) { 
  14.  
  15.       $arr2[$k] = $arr1[$i++]; 
  16.  
  17.     }else { 
  18.  
  19.       $arr2[$k] = $arr1[$j++]; 
  20.  
  21.     } 
  22.  
  23.   } 
  24.  
  25.   if($i <= $m) { 
  26.  
  27.     for(; $i <= $m$i++) { 
  28.  
  29.       $arr2[$k++] = $arr1[$i]; 
  30.  
  31.     } 
  32.  
  33.   } else if($j <= $n) { 
  34.  
  35.     for(; $j <= $n$j++) { 
  36.  
  37.       $arr2[$k++] = $arr1[$j]; 
  38.  
  39.     } 
  40.  
  41.   } 
  42.  
  43.  
  44.  
  45.  
  46. // 遞歸形式的兩路歸并 
  47.  
  48. function MSort(&$arr1, &$arr2$s$t) { 
  49.  
  50.   if($s == $t) { 
  51.  
  52.     $arr2[$s] = $arr1[$s]; 
  53.  
  54.   }else { 
  55.  
  56.     $m = floor(($s+$t)/2); 
  57.  
  58.     $tmp_arr = array(); 
  59.  
  60.     MSort($arr1$tmp_arr$s$m); 
  61.  
  62.     MSort($arr1$tmp_arr$m+1, $t); 
  63.  
  64.     Merge($tmp_arr$arr2$s$m$t); 
  65.  
  66.   } 
  67.  
  68.  
  69.  
  70. //phpfensi.com 
  71. // 對一位數組$arr[0..n-1]中的元素進行兩路歸并 
  72.  
  73. function mergeSort($arr) { 
  74.  
  75.   $len = count($arr); 
  76.  
  77.   MSort($arr$arr, 0, $len-1); 
  78.  
  79.   return $arr
  80.  

使用經驗

若排序的記錄數目n較小時,可以采用直接插入排序和簡單選擇排序,當記錄本身信息量較大時,用簡單選擇排序方法較好。

若待排序記錄按關鍵字基本有序,適合采用直接插入排序和冒泡排序。

若n值較大時,可以采用快速排序、堆排序和歸并排序。另外快速排序被認為是內部排序方法中最好的方法。

以上就是本文的全部內容,希望對大家的學習有所幫助。

Tags: php基本排序

分享到:

福利彩票25选5开奖结果