四種排序算法的PHP實(shí)現(xiàn)：
目前創(chuàng)新互聯(lián)已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、綿陽服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、霍城網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。
1)?插入排序(Insertion?Sort)的基本思想是：?
每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。
2)?選擇排序(Selection?Sort)的基本思想是：?
每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。
3)?冒泡排序的基本思想是：?
兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。
4)?快速排序?qū)嵸|(zhì)上和冒泡排序一樣，都是屬于交換排序的一種應(yīng)用。所以基本思想和上面的冒泡排序是一樣的。
1.?sort.php文件如下：
?php
class?Sort?{
private?$arr??=?array();?
private?$sort??=?'insert';
private?$marker?=?'_sort';
private?$debug?=?TRUE;
/**
*?構(gòu)造函數(shù)
*
*?@param??array??例如：
$config?=?array?(
'arr'?=?array(22,3,41,18)?,?//需要排序的數(shù)組值
'sort'?=?'insert',?//可能值:?insert,?select,?bubble,?quick
'debug'?=?TRUE?//可能值:?TRUE,?FALSE
)
*/
public?function?construct($config?=?array())?{
if?(?count($config)??0)?{
$this-_init($config);
}
}
/**
*?獲取排序結(jié)果
*/
public?function?display()?{
return?$this-arr;
}
/**
*?初始化
*
*?@param??array
*?@return?bool
*/
private?function?_init($config?=?array())?{
//參數(shù)判斷
if?(?!is_array($config)?OR?count($config)?==?0)?{
if?($this-debug?===?TRUE)?{
$this-_log("sort_init_param_invaild");
}
return?FALSE;
}
//初始化成員變量
foreach?($config?as?$key?=?$val)?{
if?(?isset($this-$key))?{
$this-$key?=?$val;
}
}
//調(diào)用相應(yīng)的成員方法完成排序
$method?=?$this-sort?.?$this-marker;
if?(?!?method_exists($this,?$method))?{
if?($this-debug?===?TRUE)?{
$this-_log("sort_method_invaild");
}
return?FALSE;
}
if?(?FALSE?===?($this-arr?=?$this-$method($this-arr)))
return?FALSE;
return?TRUE;
}
/**
*?插入排序
*?
*?@param??array
*?@return?bool
*/
private?function?insert_sort($arr)?{
//參數(shù)判斷
if?(?!?is_array($arr)?OR?count($arr)?==?0)?{
if?($this-debug?===?TRUE)?{
$this-_log("sort_array(insert)_invaild");
}
return?FALSE;
}
//具體實(shí)現(xiàn)
$count?=?count($arr);
for?($i?=?1;?$i??$count;?$i++)?{
$tmp?=?$arr[$i];
for($j?=?$i-1;?$j?=?0;?$j--)?{?
if($arr[$j]??$tmp)?{
$arr[$j+1]?=?$arr[$j];
$arr[$j]?=?$tmp;
}
}
}
return?$arr;
}
/**
*?選擇排序
*?
*?@param??array
*?@return?bool
*/
private?function?select_sort($arr)?{
//參數(shù)判斷
if?(?!?is_array($arr)?OR?count($arr)?==?0)?{
if?($this-debug?===?TRUE)?{
$this-_log("sort_array(select)_invaild");
}
return?FALSE;
}
//具體實(shí)現(xiàn)
$count?=?count($arr);
for?($i?=?0;?$i??$count-1;?$i++)?{
$min?=?$i;
for?($j?=?$i+1;?$j??$count;?$j++)?{
if?($arr[$min]??$arr[$j])?$min?=?$j;
}
if?($min?!=?$i)?{
$tmp?=?$arr[$min];
$arr[$min]?=?$arr[$i];
$arr[$i]?=?$tmp;
}
}
return?$arr;
}
/**
*?冒泡排序
*?
*?@param??array
*?@return?bool
*/
private?function?bubble_sort($arr)?{
//參數(shù)判斷
if?(?!?is_array($arr)?OR?count($arr)?==?0)?{
if?($this-debug?===?TRUE)?{
$this-_log("sort_array(bubble)_invaild");
}
return?FALSE;
}
//具體實(shí)現(xiàn)
$count?=?count($arr);
for?($i?=?0;?$i??$count;?$i++)?{
for?($j?=?$count-1;?$j??$i;?$j--)?{
if?($arr[$j]??$arr[$j-1])?{
$tmp?=?$arr[$j];
$arr[$j]?=?$arr[$j-1];
$arr[$j-1]?=?$tmp;
}
}
}
return?$arr;??
}
/**
*?快速排序
*?@by?
*?@param??array
*?@return?bool
*/
private?function?quick_sort($arr)?{
//具體實(shí)現(xiàn)
if?(count($arr)?=?1)?return?$arr;?
$key?=?$arr[0];
$left_arr?=?array();
$right_arr?=?array();
for?($i?=?1;?$i??count($arr);?$i++){
if?($arr[$i]?=?$key)
$left_arr[]?=?$arr[$i];
else
$right_arr[]?=?$arr[$i];
}
$left_arr?=?$this-quick_sort($left_arr);
$right_arr?=?$this-quick_sort($right_arr);?
return?array_merge($left_arr,?array($key),?$right_arr);
}
/**
*?日志記錄
*/
private?function?_log($msg)?{
$msg?=?'date['?.?date('Y-m-d?H:i:s')?.?']?'?.?$msg?.?'\n';
return?@file_put_contents('sort_err.log',?$msg,?FILE_APPEND);
}
}
/*End?of?file?sort.php*/
/*Location?htdocs/sort.php?*/
2.?sort_demo.php文件如下：
?php
require_once('sort.php');
$config?=?array?(
'arr'?=?array(23,?22,?41,?18,?20,?12,?200303,2200,1192)?,
//需要排序的數(shù)組值
'sort'?=?'select',
//可能值:?insert,?select,?bubble,?quick
'debug'?=?TRUE
//可能值:?TRUE,?FALSE
);
$sort?=?new?Sort($config);
//var_dump($config['arr']);
var_dump($sort-display());
/*End?of?php*/
如果你已經(jīng)使用了一段時(shí)間PHP的話，那么，你應(yīng)該已經(jīng)對(duì)它的數(shù)組比較熟悉了——這種數(shù)據(jù)結(jié)構(gòu)允許你在單個(gè)變量中存儲(chǔ)多個(gè)值，并且可以把它們作為一個(gè)集合進(jìn)行操作。
經(jīng)常，開發(fā)人員發(fā)現(xiàn)在PHP中使用這種數(shù)據(jù)結(jié)構(gòu)對(duì)值或者數(shù)組元素進(jìn)行排序非常有用。PHP提供了一些適合多種數(shù)組的排序函數(shù)，這些函數(shù)允許你在數(shù)組內(nèi)部對(duì)元素進(jìn)行排列，也允許用很多不同的方法對(duì)它們進(jìn)行重新排序。在這篇文章中我們將討論該排序中最重要的幾個(gè)函數(shù)。
簡(jiǎn)單排序
首先，讓我們來看看最簡(jiǎn)單的情況：將一個(gè)數(shù)組元素從低到高進(jìn)行簡(jiǎn)單排序，這個(gè)函數(shù)既可以按數(shù)字大小排列也可以按字母順序排列。PHP的sort（）函數(shù)實(shí)現(xiàn)了這個(gè)功能，如Listing A所示：
Listing A
?php
? $data = array(5,8,1,7,2);
? sort($data);
? print_r($data);
? ?
輸出結(jié)果如下所示：
Array ([0] = 1
[1] = 2
[2] = 5
[3] = 7
[4] = 8
)
插入排序(Insertion Sort) 是一種較穩(wěn)定 簡(jiǎn)單直觀的排序算法 插入排序的工作原理 是通過構(gòu)建有序序列 對(duì)于未排序的數(shù)據(jù) 在有序序列中從后向前掃描 找到合適的位置并將其插入 插入排序 在最好情況下 時(shí)間復(fù)雜度為O(n);在最壞情況下 時(shí)間復(fù)雜度為O(n );平均時(shí)間復(fù)雜度為O(n )
插入排序示例圖
/**
* 數(shù)據(jù)結(jié)構(gòu)與算法(PHP實(shí)現(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
復(fù)制代碼
代碼如下:
?php
/**
*
快速排序
quick
sort
*
**/
function
sort_quick($arrData)
{
if(empty($arrData)
||
!is_array($arrData))
return
false;
$flag
=
$arrData[0];
$len
=
count($arrData)
-
1;
if($len
==
0)
return
$arrData;
//
如果只有一個(gè)數(shù)據(jù)的數(shù)組直接返回
$arrLeft
=
array();
$arrRight
=
array();
$len_l
=
0;
$len_r
=
0;
for($i
=
1;
$i
=
$len;$i++)
{
if($arrData[$i]
$flag)
{
$arrLeft[$len_l]
=
$arrData[$i];
//
小于的放左邊
$len_l++;
}
else
{
$arrRight[$len_r]
=
$arrData[$i];
//
大于等于的放右邊
$len_r++;
}
}
//
合并數(shù)組
$arrResult
=
array();
if($len_l)
{
$arrLeft
=
sort_quick($arrLeft);
for($i
=
0;$i
=
$len_l
-
1;
$i++
)
{
$arrResult[$i]
=
$arrLeft[$i];
}
}
$arrResult[$len_l]
=
$flag;
$len_l++;
if($len_r)
{
$arrRight
=
sort_quick($arrRight);
for($i
=
0;$i
=
$len_r
-
1;
$i++
)
{
$arrResult[$len_l]
=
$arrRight[$i];
$len_l++;
}
}
echo
"==
",$flag,"
==========================================br/";
echo
"data
:
",print_r($arrData),"br/";
echo
"filter
left:
",print_r($arrLeft),"br/";
echo
"filter
right:
",print_r($arrRight),"br/";
echo
"return
:
",print_r($arrResult),"br/";
return
$arrResult;
}
//$list
=
array(4,3,2,1,5,7,3,7);
$list
=
array(4,51,6,73,2,5,9,33,50,3,4,6,1,4,67);
$list
=
sort_quick($list);
echo
"pre";print_r($list);
重慶分公司
重慶分公司
