本文目錄一覽：
PHP中的快速排序算法如何實現倒序?
您好，這樣的：
1. 冒泡排序法
* 思路分析：法如其名，就是像冒泡一樣，每次從數組當中 冒一個最大的數出來。
* 比如：2,4,1 // 第一次 冒出的泡是4
* 2,1,4 // 第二次 冒出的泡是 2
* 1,2,4 // 最後就變成這樣
view sourceprint?
01.$arr=array(1,43,54,62,21,66,32,78,36,76,39);
02.function getpao($arr)
03.{
04.$len=count($arr);
05.//設置一個空數組 用來接收冒出來的泡
06.//該層循環控制 需要冒泡的輪數
07.for($i=1;$i$len;$i++)
08.{ //該層循環用來控制每輪 冒出一個數 需要比較的次數
09.for($k=0;$k$len-$i;$k++)
10.{
11.if($arr[$k]$arr[$k+1])
12.{
13.$tmp=$arr[$k+1];
14.$arr[$k+1]=$arr[$k];
15.$arr[$k]=$tmp;
16.}
17.}
18.}
19.return $arr;
20.}
2. 選擇排序法：
選擇排序法思路： 每次選擇一個相應的元素，然後將其放到指定的位置
view sourceprint?
01.function select_sort($arr) {
02.//實現思路 雙重循環完成，外層控制輪數，當前的最小值。內層 控制的比較次數
03.//$i 當前最小值的位置， 需要參與比較的元素
04.for($i=0, $len=count($arr); $i$len-1; $i++) {
05.//先假設最小的值的位置
06.$p = $i;
07.//$j 當前都需要和哪些元素比較，$i 後邊的。
08.for($j=$i+1; $j$len; $j++) {
09.//$arr[$p] 是 當前已知的最小值
10.if($arr[$p] $arr[$j]) {
11.//比較，發現更小的,記錄下最小值的位置；並且在下次比較時，
12.// 應該採用已知的最小值進行比較。
13.$p = $j;
14.}
15.}
16.//已經確定了當前的最小值的位置，保存到$p中。
17.//如果發現 最小值的位置與當前假設的位置$i不同，則位置互換即可
18.if($p != $i) {
19.$tmp = $arr[$p];
20.$arr[$p] = $arr[$i];
21.$arr[$i] = $tmp;
22.}
23.}
24.//返回最終結果
25.return $arr;
26.}
3.插入排序法
插入排序法思路：將要排序的元素插入到已經 假定排序號的數組的指定位置。
view sourceprint?
01.function insert_sort($arr) {
02.//區分 哪部分是已經排序好的
03.//哪部分是沒有排序的
04.//找到其中一個需要排序的元素
05.//這個元素 就是從第二個元素開始，到最後一個元素都是這個需要排序的元素
06.//利用循環就可以標誌出來
07.//i循環控制 每次需要插入的元素，一旦需要插入的元素控制好了，
08.//間接已經將數組分成了2部分，下標小於當前的（左邊的），是排序好的序列
09.for($i=1, $len=count($arr); $i$len; $i++) {
10.//獲得當前需要比較的元素值。
11.$tmp = $arr[$i];
12.//內層循環控制 比較 並 插入
13.for($j=$i-1;$j=0;$j–) {
14.//$arr[$i];//需要插入的元素; $arr[$j];//需要比較的元素
15.if($tmp $arr[$j]) {
16.//發現插入的元素要小，交換位置
17.//將後邊的元素與前面的元素互換
18.$arr[$j+1] = $arr[$j];
19.//將前面的數設置為 當前需要交換的數
20.$arr[$j] = $tmp;
21.} else {
22.//如果碰到不需要移動的元素
23.//由於是已經排序好是數組，則前面的就不需要再次比較了。
24.break;
25.}
26.}
27.}
28.//將這個元素 插入到已經排序好的序列內。
29.//返回
30.return $arr;
31.}
4.快速排序法
view sourceprint?
01.function quick_sort($arr) {
02.//先判斷是否需要繼續進行
03.$length = count($arr);
04.if($length = 1) {
05.return $arr;
06.}
07.//如果沒有返回，說明數組內的元素個數 多餘1個，需要排序
08.//選擇一個標尺
09.//選擇第一個元素
10.$base_num = $arr[0];
11.//遍歷 除了標尺外的所有元素，按照大小關係放入兩個數組內
12.//初始化兩個數組
13.$left_array = array();//小於標尺的
14.$right_array = array();//大於標尺的
15.for($i=1; $i$length; $i++) {
16.if($base_num $arr[$i]) {
17.//放入左邊數組
18.$left_array[] = $arr[$i];
19.} else {
20.//放入右邊
21.$right_array[] = $arr[$i];
22.}
23.}
24.//再分別對 左邊 和 右邊的數組進行相同的排序處理方式
25.//遞歸調用這個函數,並記錄結果
26.$left_array = quick_sort($left_array);
27.$right_array = quick_sort($right_array);
28.//合併左邊 標尺 右邊
29.return array_merge($left_array, array($base_num), $right_array);
30.}
php幾種排序算法實例詳解
四種排序算法的PHP實現：
1) 插入排序(Insertion Sort)的基本思想是：
每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。
2) 選擇排序(Selection Sort)的基本思想是：
每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子文件的最後，直到全部記錄排序完畢。
3) 冒泡排序的基本思想是：
兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。
4) 快速排序實質上和冒泡排序一樣，都是屬於交換排序的一種應用。所以基本思想和上面的冒泡排序是一樣的。
1. sort.php文件如下：
?php
class Sort {
private $arr = array();
private $sort = ‘insert’;
private $marker = ‘_sort’;
private $debug = TRUE;
/**
* 構造函數
*
* @param array 例如：
$config = array (
‘arr’ = array(22,3,41,18) , //需要排序的數組值
‘sort’ = ‘insert’, //可能值: insert, select, bubble, quick
‘debug’ = TRUE //可能值: TRUE, FALSE
)
*/
public function construct($config = array()) {
if ( count($config) 0) {
$this-_init($config);
}
}
/**
* 獲取排序結果
*/
public function display() {
return $this-arr;
}
/**
* 初始化
*
* @param array
* @return bool
*/
private function _init($config = array()) {
//參數判斷
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;
}
}
//調用相應的成員方法完成排序
$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) {
//參數判斷
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this-debug === TRUE) {
$this-_log(“sort_array(insert)_invaild”);
}
return FALSE;
}
//具體實現
$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) {
//參數判斷
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this-debug === TRUE) {
$this-_log(“sort_array(select)_invaild”);
}
return FALSE;
}
//具體實現
$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) {
//參數判斷
if ( ! is_array($arr) OR count($arr) == 0) {
if ($this-debug === TRUE) {
$this-_log(“sort_array(bubble)_invaild”);
}
return FALSE;
}
//具體實現
$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) {
//具體實現
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) ,
//需要排序的數組值
‘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*/
php快速排序算法
?php
function quick_sort($arr) {
// 判斷是否需要繼續
if (count($arr) = 1) {
return $arr;
}
$middle = $arr[0]; // 中間值
$left = array(); // 小於中間值
$right = array();// 大於中間值
// 循環比較
for ($i=1; $i count($arr); $i++) {
if ($middle $arr[$i]) {
// 大於中間值
$right[] = $arr[$i];
} else {
// 小於中間值
$left[] = $arr[$i];
}
}
// 遞歸排序兩邊
$left = quick_sort($left);
$right = quick_sort($right);
// 合併排序後的數據，別忘了合併中間值
return array_merge($left, array($middle), $right);
}
$arr = array(25,133,452,364,5876,293,607,365,8745,534,18,33);
echo ‘pre’;
var_dump($arr);
var_dump(quick_sort($arr));
PHP快速排序算法實現的原理及代碼詳解
算法原理
下列動圖來自五分鐘學算法，演示了快速排序算法的原理和步驟。
步驟:
從數組中選個基準值
將數組中大於基準值的放同一邊、小於基準值的放另一邊，基準值位於中間位置
遞歸的對分列兩邊的數組再排序
代碼實現
function
quickSort($arr)
{
$len
=
count($arr);
if
($len
=
1)
{
return
$arr;
}
$v
=
$arr[0];
$low
=
$up
=
array();
for
($i
=
1;
$i
$len;
++$i)
{
if
($arr[$i]
$v)
{
$up[]
=
$arr[$i];
}
else
{
$low[]
=
$arr[$i];
}
}
$low
=
quickSort($low);
$up
=
quickSort($up);
return
array_merge($low,
array($v),
$up);
}
測試代碼:
$startTime
=
microtime(1);
$arr
=
range(1,
10);
shuffle($arr);
echo
“before
sort:
“,
implode(‘,
‘,
$arr),
“\n”;
$sortArr
=
quickSort($arr);
echo
“after
sort:
“,
implode(‘,
‘,
$sortArr),
“\n”;
echo
“use
time:
“,
microtime(1)
–
$startTime,
“s\n”;
測試結果:
before
sort:
1,
7,
10,
9,
6,
3,
2,
5,
4,
8
after
sort:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
use
time:
0.0009009838104248s
時間複雜度
快速排序的時間複雜度在最壞情況下是O(N2)，平均的時間複雜度是O(N*lgN)。
這句話很好理解：假設被排序的數列中有N個數。遍歷一次的時間複雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。
1)
為什麼最少是lg(N+1)次？快速排序是採用的分治法進行遍歷的，我們將它看作一棵二叉樹，它需要遍歷的次數就是二叉樹的深度，而根據完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數最少是lg(N+1)次。
2)
為什麼最多是N次？這個應該非常簡單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數最多是N次。
您可能感興趣的文章:PHP快速排序算法實例分析PHP四種排序算法實現及效率分析【冒泡排序,插入排序,選擇排序和快速排序】PHP排序算法之快速排序(Quick
Sort)及其優化算法詳解PHP遞歸實現快速排序的方法示例php
二維數組快速排序算法的實現代碼PHP常用排序算法實例小結【基本排序，冒泡排序，快速排序，插入排序】PHP快速排序quicksort實例詳解
PHP實現常見的排序算法
註：為方便描述，下面的排序全為正序（從小到大排序）
假設有一個數組[a,b,c,d]
冒泡排序依次比較相鄰的兩個元素，如果前面的元素大於後面的元素，則兩元素交換位置；否則，位置不變。具體步驟：
1，比較a,b這兩個元素，如果ab,則交換位置，數組變為：[b,a,c,d]
2，比較a,c這兩個元素，如果ac,則位置不變，數組變為：[b,a,c,d]
3，比較c,d這兩個元素，如果cd,則交換位置，數組變為：[b,a,d,c]
完成第一輪比較後，可以發現最大的數c已經排（冒）在最後面了，接着再進行第二輪比較，但第二輪比較不必比較最後一個元素了，因為最後一個元素已經是最大的了。
第二輪比較結束後，第二大的數也會冒到倒數第二的位置。
依次類推，再進行第三輪，，，
就這樣最大的數一直往後排（冒），最後完成排序。所以我們稱這種排序算法為冒泡排序。
選擇排序是一種直觀的算法，每一輪會選出列中最小的值，把最小值排到前面。具體步驟如下:
插入排序步驟大致如下：
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來，且在大部分真實世界的數據，可以決定設計的選擇，減少所需時間的二次方項之可能性。
步驟：
從數列中挑出一個元素，稱為 「基準」（pivot），
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/278847.html
微信掃一掃 
支付寶掃一掃 