快速排序
理解：
快速排序兩個關鍵點：選取基準和mark指針
基準循環(huán)不變仍律，基準與數(shù)組元素比較，滿足條件mark指針進位交換 毅该，mark指針指定的元素值一定小于或者等于基準值（當從小到大排時）
最后交換基準和mark指針元素，將數(shù)組切割菇篡，遞歸重復上述過程
同冒泡排序一樣顿涣，快速排序也屬于交換排序波闹，通過元素之間的比較和交換位置來達到排序的目的。
不同的是涛碑，冒泡排序在每一輪中只把1個元素冒泡到數(shù)列的一端精堕，而快速排序則在每一輪挑選一個基準元素，并讓其他比它大的元素移動到數(shù)列一邊蒲障，比它小的元素移動到數(shù)列的另一邊歹篓，從而把數(shù)列拆解成兩個部分。
image.png
這種思路就叫作分治法揉阎。
具體如何實現(xiàn)呢庄撮？有兩種方法。
1. 雙邊循環(huán)法毙籽。
2. 單邊循環(huán)法洞斯。
單邊循環(huán)法比雙邊循環(huán)更容易理解和運用，這里只介紹單邊循環(huán)法
首先選定基準元素pivot坑赡。同時烙如，設置一個mark指針指向數(shù)列起始位置，這個mark指針代表小于基準元素的區(qū)域邊界毅否。
image.png
接下來亚铁，從基準元素的下一個位置開始遍歷數(shù)組。
如果遍歷到的元素大于基準元素螟加，就繼續(xù)往后遍歷徘溢。
如果遍歷到的元素小于基準元素，則需要做兩件事：第一仰迁，把mark指針右移1位甸昏，因為小于pivot的區(qū)域邊界增大了1；第二徐许，讓最新遍歷到的元素和mark指針所在位置的元素交換位置施蜜，因為最新遍歷的元素歸屬于小于pivot的區(qū)域。首先遍歷到元素7雌隅，7>4翻默，所以繼續(xù)遍歷。
image.png
接下來遍歷到的元素是3恰起，3<4修械，所以mark指針右移1位。
image.png
隨后检盼，讓元素3和mark指針所在位置的元素交換肯污，因為元素3歸屬于小于pivot的區(qū)域。
image.png
image.png
按照這個思路，繼續(xù)遍歷蹦渣，后續(xù)步驟如圖所示哄芜。
image.png
具體代碼運用了遞歸
詳情如下:
class Code{
function quickSort(&$arr,$intStart,$intEnd){
// 遞歸結束條件：startIndex大于或等于endIndex時
if($intStart >= $intEnd){
return;
}
// 根據(jù)基準元素，分成兩部分進行遞歸排序
$mark = $this->positionMark($arr,$intStart,$intEnd);
// 根據(jù)基準元素柬唯，分成兩部分進行遞歸排序
$this->quickSort($arr,$intStart,$mark-1);
$this->quickSort($arr,$mark+1,$intEnd);
}
/**
* 分治（單邊循環(huán)法）
* @param arr 待交換的數(shù)組
* @param intStart 起始下標
* @param intEnd 結束下標
*/
function positionMark(&$arr,$intStart,$intEnd){
//以數(shù)組首位作為基準
$base = $arr[$intStart];
//mark起始為數(shù)組首位
//mark指針的作用就是使mark指針的左邊小于等于基準认臊，右邊大于基準
$mark = $intStart;
//遍歷數(shù)組從基準的后一位與基準對比，直到數(shù)組的最后一個
for($i=$intStart+1;$i<=$intEnd;$i++){
//因為是從小到大排序
//故如果比基準小锄奢，元素與mark下標值互換失晴，移動到左邊
if($arr[$i] < $base){
//mark標記的值永遠小于或者等于基準值的
//mark向前移動一位則是大于基準值的，發(fā)生交換則是把大值換到后邊拘央，小值放到前邊
$mark++;
$tmp = $arr[$mark];
$arr[$mark] = $arr[$i];
$arr[$i] = $tmp;
}
}
//最后替換基準和mark
$arr[$intStart] = $arr[$mark];
$arr[$mark] = $base;
return $mark;
}
//運行
function run(){
$arr = array(8,5,7,4,2,0,1,3,9);
$this->quickSort($arr,0,count($arr)-1);
print_r($arr);
}
}
$obj = new Code();
$obj->run();
輸出結果：
image.png
