注：為方便描述，下面的排序全為正序（從小到大排序）
創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的棗莊網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
假設(shè)有一個數(shù)組[a,b,c,d]
冒泡排序依次比較相鄰的兩個元素，如果前面的元素大于后面的元素，則兩元素交換位置；否則，位置不變。具體步驟：
1，比較a,b這兩個元素，如果ab,則交換位置，數(shù)組變?yōu)椋篬b,a,c,d]
2，比較a,c這兩個元素，如果ac,則位置不變，數(shù)組變?yōu)椋篬b,a,c,d]
3，比較c,d這兩個元素，如果cd,則交換位置，數(shù)組變?yōu)椋篬b,a,d,c]
完成第一輪比較后，可以發(fā)現(xiàn)最大的數(shù)c已經(jīng)排（冒）在最后面了，接著再進行第二輪比較，但第二輪比較不必比較最后一個元素了，因為最后一個元素已經(jīng)是最大的了。
第二輪比較結(jié)束后，第二大的數(shù)也會冒到倒數(shù)第二的位置。
依次類推，再進行第三輪，，，
就這樣最大的數(shù)一直往后排（冒），最后完成排序。所以我們稱這種排序算法為冒泡排序。
選擇排序是一種直觀的算法，每一輪會選出列中最小的值，把最小值排到前面。具體步驟如下:
插入排序步驟大致如下：
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來，且在大部分真實世界的數(shù)據(jù)，可以決定設(shè)計的選擇，減少所需時間的二次方項之可能性。
步驟：
從數(shù)列中挑出一個元素，稱為 “基準”（pivot），
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
插入排序(Insertion Sort) 是一種較穩(wěn)定 簡單直觀的排序算法 插入排序的工作原理 是通過構(gòu)建有序序列 對于未排序的數(shù)據(jù) 在有序序列中從后向前掃描 找到合適的位置并將其插入 插入排序 在最好情況下 時間復(fù)雜度為O(n);在最壞情況下 時間復(fù)雜度為O(n );平均時間復(fù)雜度為O(n )
插入排序示例圖
/**
* 數(shù)據(jù)結(jié)構(gòu)與算法(PHP實現(xiàn)) - 插入排序(Insertion Sort)。Tw.WiNGwit
*
* @author 創(chuàng)想編程(TOPPHP.ORG)
* @copyright Copyright (c) 2013 創(chuàng)想編程(TOPPHP.ORG) All Rights Reserved
* @license /licenses/mit-license.php MIT LICENSE
* @version 1.0.0 - Build20130613
*/
class InsertionSort {
/**
* 需要排序的數(shù)據(jù)數(shù)組。
*
* @var array
*/
private $data;
/**
* 數(shù)據(jù)數(shù)組的長度。
*
* @var integer
*/
private $size;
/**
* 數(shù)據(jù)數(shù)組是否已排序。
*
* @var boolean
*/
private $done;
/**
* 構(gòu)造方法 - 初始化數(shù)據(jù)。
*
* @param array $data 需要排序的數(shù)據(jù)數(shù)組。
*/
public function __construct(array $data) {
$this-data = $data;
$this-size = count($this-data);
$this-done = FALSE;
}
/**
* 插入排序。
*/
private function sort() {
$this-done = TRUE;
for ($i = 1; $i $this-size; ++$i) {
$current = $this-data[$i];
if ($current $this-data[$i - 1]) {
for ($j = $i - 1; $j = 0 $this-data[$j] $current; --$j) {
$this-data[$j + 1] = $this-data[$j];
}
$this-data[$j + 1] = $current;
}
}
}
/**
* 獲取排序后的數(shù)據(jù)數(shù)組。
*
* @return array 返回排序后的數(shù)據(jù)數(shù)組。
*/
public function getResult() {
if ($this-done) {
return $this-data;
}
$this-sort();
return $this-data;
}
}
?
示例代碼 1
2
3
4
$insertion = new InsertionSort(array(9, 1, 5, 3, 2, 8, 6));
echo '
', print_r($insertion-getResult(), TRUE), '
'; lishixinzhi/Article/program/PHP/201311/20783
可以使用自定義函數(shù)排序uasort(),搭配匿名函數(shù)挺方便的
$array = array('a' = 4, 'b' = 8, 'c' = -1, 'd' = -9, 'e' = 2, 'f' = 5, 'g' = 3, 'h' = -4);
uasort($array,function($a,$b){
if ($a == $b) {
return 0;
}
return ($a $b) ? -1 : 1;
});
print_r($array);
常見的php排序算法
本文匯總了常見的php排序算法，在進行算法設(shè)計的時候有不錯的借鑒價值?，F(xiàn)分享給大家供參考之用。具體如下：
一、插入排序
用文字簡單的描述，比如說$arr = array(4,2,4,6,3,6,1,7,9); 這樣的一組數(shù)字進行順序排序：
那么，首先，拿數(shù)組的第二個元素和第一元素比較，假如第一個元素大于第二元素，那么就讓兩者位置互換，接下來，拿數(shù)組的第三個元素，分別和第二個，第一個元素比較，假如第三個元素小，那么就互換。依次類推。這就是插入排序,它的時間頻度是：1+2+...+(n-1)=(n^2)/2。則它的時間復(fù)雜度為O(n^2).
php實現(xiàn)代碼如下：
?phpfunction Sort($arr){ $count = count($arr); if($count2){ return $arr; } for($i=1;$i$count;$i++){ tmp="$arr[$i];" j=""=0$arr[$j]$arr[$i]){ return=""
二、選擇排序
選擇排序用語言描述的話，可以這樣,如：$arr = array(4,3,5,2,1);
首先,拿第一個和后面所有的比，找出最小的那個數(shù)字，然后和第一個數(shù)組互換（當然，如果是第一個最小，那么就不用互換了），接著循環(huán)，即：拿第二個和后面的比較，找出最小的數(shù)字，然后和第二個數(shù)字互換，依次類推，也就是說每次都是找出剩余最小的值。 可得到：第一次，時間頻度 是n, （第一個和后面的n－1個比較，找到最小的，再看是不是第一個，不是第一個的話進行互換） 在往后，依次是 減一 。 它的時間復(fù)雜度，也是O(n^2);
php實現(xiàn)代碼如下：
?phpfunction selectSort($arr){ $count = count($arr); if($count2){ return $arr; } for($i=0;$i$count;$i++){ $min=$i; for(j=$i+1;$j$count;$j++){$arr[$j]){ $min = $j; //找到最小的那個元素的下標 } } if($min!=$i){//如果下標不是$i 則互換。 $tmp= $arr[$i]; $arr[$i] = $arr[$min]; $arr[$min] = $tmp; } } return $arr; }?
三、冒泡排序
冒泡排序其實上是和選擇排序相比，并無明顯差別。都是找到最小的，放到最左端。依次循環(huán)解決問題。差別在于冒泡排序的交換位置的次數(shù)較多，而選擇排序則是找到最小的元素的下標，然后直接和最左端的交換位置。
php實現(xiàn)代碼如下：
?phpfunction selectSort($arr){ $count = count($arr); if($count2){ return $arr; } for($i=0;$i$count;$i++){ for(j=$i+1;$j$count;$j++){$arr[$j]){ $tmp= $arr[$i]; $arr[$i] = $arr[$i]; $arr[$i] = $tmp; } } } return $arr; }?
四、快速排序
快速排序，用語言來形容的話，從數(shù)組中選擇一個值$a，然后和其余元素進行比較，比$a大的放到數(shù)組right中，反之，放到數(shù)組left中。然后將left right 分別進行遞歸調(diào)用，即：再細分left right ，最后進行數(shù)組的合并。
php實現(xiàn)快速排序：
?phpfunction mySort($arr){ $count = count($arr); if($count2){ return $arr; } $key = $arr[0];//選擇第一個元素作為比較元素，可選其他 $left = array(); $right = array(); for($i=1;$i$count;$i++){ key=""=$arr[$i]){ $left[] = $arr[$i]; }else{ $right[] = $arr[$i]; } } $left = mySort($left); $right = mySort($right); $result = array_merge($left,$right); return $result; }?
五、歸并排序
其實歸并排序是一種拆分，合并的思想。和快速排序思想有共通之處，左邊一堆，右邊一堆，然后進行合并。通過遞歸實現(xiàn)排序。 區(qū)別之處呢？ 他們的區(qū)別也是思想上本質(zhì)的區(qū)別，快速排序的拆分，是選擇了特定的值進行大小比較，從而分為left 和 right 。也就是小的一堆放入left，大的一堆放入right。而后，小的left 再細分為left1 right1。。。。通過進行類似的遞歸完成排序。也就是說，一直細分下去，遞歸最末尾的left1就是最小值。
而歸并排序，是從幾何上的左右切分，一直遞歸切分成2或者1的'最小粒度的數(shù)組，然后才開始進行比較大小，然后合并。此處的比較大小是：兒子left的元素 和兒子的right元素 進行比較，而后進行排序合并成為父親left或者right。在此，直到拿到各自排序合并完成最后兩個數(shù)組：最起初的left 和right，也僅僅直到他們各自的順序，并不能確認整個數(shù)組的順序，還是需要通過最終的left right 比較后合并才能完成真正意義上的排序。
?phpfunction gbSort($arr){ if(count($arr)=1){return min="floor(count($arr)/2);//取中間數(shù)字進行拆分" left="gbSort($left);" right="gbSort($right);" return="" function=""$right[0] ? array_shift($right) : array_shift($left); //進行比較，小的移除，并且放入到數(shù)組$m中。 } return arr_merge($m,$left,$right);//進行合并（由于不知道left right 哪個會為空，所以進行統(tǒng)一合并）}?
六、堆排序
本例中fixDown函數(shù)實現(xiàn)對某一個節(jié)點的向下調(diào)整，這里默認的是起始節(jié)點為1，方便計算父子節(jié)點關(guān)系
注:
起始節(jié)點為1的父子關(guān)系: 父節(jié)點k, 子節(jié)點為2K、2k+1 子節(jié)點j, 父節(jié)點為 floor(j/2) floor為向下取整
起始節(jié)點為0的父子關(guān)系: 父節(jié)點k, 子節(jié)點為2K+1, 2k+2 子節(jié)點j, 父節(jié)點為 floor((j-1)/2)
參數(shù)$k為調(diào)整點位置, $lenth為數(shù)組長度，也就是從1起始到最后一個節(jié)點的坐標.
?phpfunction fixDown($arr, $k, $lenth){while(2*$k=$lenth) { //只要當前節(jié)點有子節(jié)點， 就需要繼續(xù)該循環(huán) $j = $k*2; if ($j$lenth $arr[$j]$arr[$j+1]) $j++; // 只要子節(jié)點有右節(jié)點，且右節(jié)點比左節(jié)點大，那么切換到右節(jié)點操作。 if ($arr[$j] $arr[$k]) break; // 如果子節(jié)點都沒有父節(jié)點大， 那么調(diào)整結(jié)束。 exch($arr[$j], $arr[$k]); $k = $j; }}function exch($a, $b) { $tmp = $a; $a = $b; $b = $tmp;}function headSort($arr){ $len = count($arr); array_unshift($arr, NULL); for($i=$len/2;$i=1;$i--) { fixDown($arr, $i, $len); } while($len1) { exch($arr[1], $arr[$len]); fixDown($arr, 1, --$len); } array_shift($arr);}$arr = array(4,6,4,9,2,3);headSort($arr);?
希望本文所述排序算法實例對大家的php程序設(shè)計有所幫助。
;
重慶分公司
重慶分公司
