資訊專欄INFORMATION COLUMN
摘要：直接默寫出快速排序還是有一定難度的，所以一定要弄清楚原理再去記憶而不是去硬背。快速排序是于年提出的一種劃分交換排序。
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用，因此在很多筆試面試中出現(xiàn)的幾率很高。
直接默寫出快速排序還是有一定難度的，所以一定要弄清楚原理再去記憶而不是去硬背。
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-Conque)。
最常見的實現(xiàn)方法是"填坑法"，它的實現(xiàn)步驟如下：
選定數(shù)列頭元素為基準(zhǔn)元素pivot，并記住這個位置index，這個位置相當(dāng)于一個"坑"。
設(shè)置兩個指針left和right，分別指向數(shù)列的最左和最右兩個元素。
接下來從right指針開始，把指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較，如果比pivot大，則right指針向左移動；如果比pivot小，則把所指向的元素放入index對應(yīng)的位置。
將被放入坑中的元素(right指針移動之前指向的元素)之前的位置賦值給index讓這個位置變成一個新的"坑"，同時left指針向右移動一位。
接下來切換到left指針進(jìn)行比較，如果left當(dāng)前指向的元素小于pivot，則left指針向右移動；如果元素大于pivot，則把元素放入坑中，left指向的位置賦值給index，使其變成一個新的"坑"，同時right指針向左移動一位。
重復(fù)步驟3，4，5直到left等于right時，將pivot放入left和right重合的位置，此時數(shù)列中比pivot小的元素都在pivot左邊，比pivot大的都在pivot元素位置的右邊。
獲取pivot的位置pivotIndex，分而制之，將pivotIndex左側(cè)和右側(cè)的子數(shù)列分別重復(fù)上述步驟1～6，直到不能拆分子數(shù)列為止，整個數(shù)列就是一個從頭開始遞增的數(shù)列。
具體的代碼實現(xiàn)如下：
= $left) {
// right 指針從右向左進(jìn)行移動，如果當(dāng)前值小于基準(zhǔn)值則將當(dāng)前元素放到坑中，當(dāng)前元素的位置變成新坑，left向右移動一個位置，切換到left進(jìn)行比較，否則right往左移動一個位置繼續(xù)用新元素的值與基準(zhǔn)值進(jìn)行比較
while ($right >= $left) {
if ($arr[$right] < $pivot) {
$arr[$dataIndex] = $arr[$right];
$dataIndex = $right;
$left++;
break;
}
$right--;
}
// left 指針從左往右移動，如果當(dāng)前值大于基準(zhǔn)值則將當(dāng)前元素放到坑中，當(dāng)前元素變?yōu)樾驴?，right向左移動一個位置，切換到right進(jìn)行比較，否則left往右移動一個位置繼續(xù)與基準(zhǔn)值進(jìn)行比較
while($right >= $left) {
if ($arr[$left] > $pivot) {
$arr[$dataIndex] = $arr[$left];
$dataIndex = $left;
$right --;
break;
}
$left ++;
}
}
$arr[$dataIndex] = $pivot;
return $dataIndex;
}
public function quickSort(&$arr, $startIndex, $endIndex)
{
// startIndex大于等于endIndex的時候遞歸結(jié)束
if ($startIndex >= $endIndex) {
return ;
}
$pivotIndex = $this->partition($arr, $startIndex, $endIndex);
$this->quickSort($arr, $startIndex, $pivotIndex - 1);
$this->quickSort($arr, $pivotIndex + 1, $endIndex);
}
}
$quickSortClass = new quickSortClass();
$arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85];
$quickSortClass->quickSort($arr, 0, count($arr) - 1);
var_dump($arr);
填坑法的口訣如下
1．$left=strart; $right = end; $pivot=$arr[$left]; 第一個坑為$arr[$left]
2．$right--由后向前找比$pivot小的數(shù)，找到后挖出此數(shù)填到前一個坑$arr[$left]中， $arr[$right]變成新坑。
3．$left++由前向后找比$pivot大的數(shù)，找到后也挖出此數(shù)填到前一個坑$arr[$right]中。
4．重復(fù)執(zhí)行2，3二步，直到$left==$right，將基準(zhǔn)數(shù)$pivot填入$arr[$left]中。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/31302.html
摘要：經(jīng)過一次冒泡排序，最終在無序表中找到一個最大值，第一次冒泡結(jié)束。也是我們后面要說的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán)，而不會執(zhí)行第二層循環(huán)。因此冒泡排序的時間復(fù)雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要：同步異步回調(diào)傻傻分不清楚。分割線上面主要講了同步和回調(diào)執(zhí)行順序的問題，接著我就舉一個包含同步異步回調(diào)的例子。同步優(yōu)先回調(diào)內(nèi)部有個，第二個是一個回調(diào)回調(diào)墊底。異步也，輪到回調(diào)的孩子們回調(diào)，出來執(zhí)行了。 同步、異步、回調(diào)？傻傻分不清楚。 大家注意了，教大家一道口訣： 同步優(yōu)先、異步靠邊、回調(diào)墊底（讀起來不順） 用公式表達(dá)就是： 同步 => 異步 => 回調(diào) 這口訣有什么用呢？用來對付面試的...
摘要：同步異步回調(diào)傻傻分不清楚。分割線上面主要講了同步和回調(diào)執(zhí)行順序的問題，接著我就舉一個包含同步異步回調(diào)的例子。同步優(yōu)先回調(diào)內(nèi)部有個，第二個是一個回調(diào)回調(diào)墊底。異步也，輪到回調(diào)的孩子們回調(diào)，出來執(zhí)行了。 同步、異步、回調(diào)？傻傻分不清楚。 大家注意了，教大家一道口訣： 同步優(yōu)先、異步靠邊、回調(diào)墊底（讀起來不順） 用公式表達(dá)就是： 同步 => 異步 => 回調(diào) 這口訣有什么用呢？用來對付面試的...
摘要：程序效果九乘九口訣表乘法口訣表在這里我用兩幅運(yùn)行效果給大家看看，這樣就知道不同之處了。乘法口訣表題目內(nèi)容實現(xiàn)一個函數(shù)，打印乘法口訣表，口訣表的行數(shù)和列數(shù)自己指定。其實大致的性質(zhì)是跟乘法口訣表一樣都是使用循環(huán)嵌套。 大家好，我是澤奀。這篇文章的代碼是C語言中比較簡單的程序，也是初學(xué)者必要學(xué)會的...
閱讀 2678·2021-10-14 09:42
閱讀 1216·2021-09-22 15:09
閱讀 3632·2021-09-09 09:33
閱讀 3093·2021-09-07 09:59
閱讀 3733·2021-09-03 10:34
閱讀 3683·2021-07-26 22:01
閱讀 2885·2019-08-30 13:06
閱讀 1266·2019-08-30 10:48
