題記：
- 常見的排序算法有：冒泡排序法覆山，快速排序法，選擇排序法奇唤，插入排序法，此處作為自己最近面試準備進行的學習筆記匹摇，同時也希望能幫到你咬扇。
- 需求：將一個有多個數(shù)字的數(shù)組進行從小到大的排序.
排序算法
【一】.冒泡排序
- 思路分析：
想象一個大水池里有N多還未排好的序列的氫氣球，較大的先冒出來廊勃，然后依次是較小的往上冒懈贺。即，每次比較相鄰的兩個數(shù)坡垫，小的在前大的在后，否則進行位置互換。
image
- 代碼實現(xiàn)：（舉例幾種寫法尼桶，注意循環(huán)體的判斷條件）建議使用第一褐奴、二種。
/**
* 交換方法
* @param array $arr 目標數(shù)組
* @param $a 索引a
* @param $b 索引b
* @param bool $flag 交換標志
* @return bool
*/
function swap(array &$arr,$a,$b,$flag = false){
// 遍歷i后面的元素溉卓，只要該元素小于當前元素皮迟，就把較小的往前冒泡
if($arr[$a] > $arr[$b]){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
$flag = true;
}
return $flag;
}
/**
* 第一種寫法
* @param $arr 所要排序的數(shù)組
* @return mixed 返回的數(shù)組
*/
function bubbleSort($arr) {
$len = count($arr);
if ($len <= 1) {return $arr;}
//該層循環(huán)控制 需要冒泡的輪數(shù)
for ($i = 0; $i < $len-1; $i++) {
//該層循環(huán)用來控制每輪 冒出一個數(shù) 需要比較的次數(shù)
for ($j = $i + 1; $j < $len; $j++) {
// 或者 $this->swap($arr,$j,$j+1);
$this->swap($arr,$i,$j);
}
}
return $arr;
}
//第二種寫法
public function BubbleSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0;$i < $len-1;$i++){
//TODO 本趟排序開始前，交換標志應為假
$flag = false;
for ($j = 0;$j <= $len-2;$j++){
$flag = $this->swap($arr,$j,$j+1,$flag);
}
if(!$flag) return $arr;
}
return $arr;
}
//第三種寫法
function BubbleSort3(array &$arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++){
//從后往前逐層上浮小的元素 $j >= 0
for($j = $len - 2;$j >= $i ;$j --){
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
//第四種寫法
function bubbleSort4($arr)
{
$len = count($arr);
if ($len <= 1) {return $arr;}
for($i = 0;$i < $len-1;$i++) {
for($j = 0;$j < $len-$i-1;$j++) {
$this->swap($arr,$j,$j+1);
}
}
return $arr;
}
- 小結：
- 時間復雜度：O(n^2)
- 補充：可使用PHP內置函數(shù)
sort()或rsort(). - 上述函數(shù)對索引數(shù)組按照鍵值進行排序桑寨，為 array 中的單元賦予新的鍵名伏尼，這將刪除原有的鍵名而不僅是重新排序。如果成功則返回 TRUE尉尾，否則返回 FALSE
【二】.選擇排序
- 思路分析：
每一次從待排序的數(shù)據(jù)元素中選出最斜住（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
image
- 代碼實現(xiàn)
/*
* @param 選擇排序法
* 每一次從待排序的數(shù)據(jù)元素中選出最腥潘（或最大）的一個元素兽掰，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
* */
function selectSort($arr){
//雙重循環(huán)完成徒役，外層控制輪數(shù)孽尽，內層控制比較次數(shù)
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0; $i < $len-1; $i++) {
$minIndex = $i;
// 找出i后面最小的元素與當前元素交換
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$minIndex] > $arr[$j]){
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
- 小結：
- 時間復雜度：O(n^2)
- 不穩(wěn)定的排序方法（比如序列[5， 5忧勿， 3]第一次就將第一個[5]與[3]交換杉女，導致第一個5挪動到第二個5后面）。
- 在一趟選擇鸳吸，如果一個元素比當前元素小熏挎，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了
- 最好情況是晌砾，已經(jīng)有序坎拐，交換0次；最壞情況交換n-1次养匈，逆序交換n/2次哼勇。交換次數(shù)比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多呕乎，n值較小時积担，選擇排序比冒泡排序快
【三】.插入排序
- 思路分析：
- 每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上猬仁，直到全部插入完為止帝璧。(從而得到一個新的、個數(shù)加一的有序數(shù)據(jù))
- 描述：
- ⒈ 從第一個元素開始湿刽，該元素可以認為已經(jīng)被排序
- ⒉ 取出下一個元素的烁，在已經(jīng)排序的元素序列中從后向前掃描
- ⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
- ⒋ 重復步驟3叭爱，直到找到已排序的元素小于或者等于新元素的位置
- ⒌ 將新元素插入到下一位置中
- ⒍ 重復步驟 2~5
image
- 代碼實現(xiàn)
- 此處提供兩種寫法撮躁，主要是循環(huán)的寫法稍有不同，可作參考.
/*
* 插入排序法
* 每步將一個待排序的記錄买雾，按其關鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上把曼，直到全部插入完為止。
* */
function insertSort($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默認$array[0]漓穿，已經(jīng)有序嗤军，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是準備插入的數(shù)
$insertIndex = $i - 1; //有序表中準備比較的數(shù)的下標
while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
$arr[$insertIndex + 1] = $arr[$insertIndex]; //將數(shù)組往后挪
$insertIndex--; //將下標往前挪，準備與前一個進行比較
}
if($insertIndex + 1 !== $i){
$arr[$insertIndex + 1] = $insertVal;
}
}
}
return $arr;
}
function insertSort2($arr){
$len = count($arr);
if ($len <= 1) {return $arr;}
//先默認$array[0]晃危，已經(jīng)有序叙赚，是有序表
for($i = 1;$i < $len;$i++){
if ($arr[$i] < $arr[$i-1]){
$insertVal = $arr[$i]; //$insertVal是準備插入的數(shù)
//$j 有序表中準備比較的數(shù)的下標
//$j-- 將下標往前挪老客，準備與前一個進行比較
for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
$arr[$j+1]= $arr[$j];//將數(shù)組往后挪
}
$arr[$j + 1] = $insertVal;
}
}
return $arr;
}
- 小結：
- 時間復雜度：O(n^2)
- 空間復雜度：O(1) (用于記錄需要插入的數(shù)據(jù))
- 穩(wěn)定的排序方法
- 算法適用于少量數(shù)據(jù)的排序
- 如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目震叮。該算法可以認為是插入排序的一個變種胧砰，稱為二分查找排序。
【四】.快速排序
- 思路分析：
- 通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分苇瓣，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小尉间，
- 然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行击罪，以此達到整個數(shù)據(jù)變成有序序列
image
- 代碼實現(xiàn)
- 注：網(wǎng)上多數(shù)為
quick_sort2（）這類的寫法哲嘲，感覺并非原算法的描述，建議可做參考. - 或許代碼
quick_sort()有所欠缺媳禁，并未發(fā)現(xiàn)能有較快的排序效果眠副，尷尬了.
- 注：網(wǎng)上多數(shù)為
/**
* @param $arr 目標數(shù)組
* @param int $l 左起坐標
* @param $r 右起坐標 初始化傳入數(shù)組時，$r = count($arr)-1
* @return mixed
*/
public function quick_sort(&$arr, $l=0, $r)
{
$length = count($arr);
//先判斷是否需要繼續(xù)進行 遞歸出口:數(shù)組長度為1竣稽，直接返回數(shù)組
if(!is_array($arr)||$length <= 1) {return $arr;}
if ($l < $r)
{
$i = $l;
$j = $r;
$baseVal = $arr[$l];
while ($i < $j)
{
// 從右向左找第一個小于$baseVal的數(shù)
while($i < $j && $arr[$j] >= $baseVal)
$j--;
if($i < $j)
$arr[$i++] = $arr[$j];
// 從左向右找第一個大于等于$baseVal的數(shù)
while($i < $j && $arr[$i] < $baseVal)
$i++;
if($i < $j)
$arr[$j--] = $arr[$i];
}
$arr[$i] = $baseVal;
$this->quick_sort($arr, $l, $i - 1); // 遞歸調用
$this->quick_sort($arr, $i + 1, $r);
return $arr;
}
}
/*
* 快速排序法
* */
public function quick_sort2($arr) {
$length = count($arr);
//先判斷是否需要繼續(xù)進行 遞歸出口:數(shù)組長度為1囱怕，直接返回數(shù)組
if(!is_array($arr)||$length <= 1) {return $arr;}
//選擇第一個元素作為基準
$baseValue = $arr[0];
//遍歷除了標尺外的所有元素，按照大小關系放入兩個數(shù)組內
//初始化兩個數(shù)組
$leftArr = array(); //小于基準的
$rightArr = array(); //大于基準的
//使用for循環(huán)進行遍歷丧枪，把選定的基準當做比較的對象
for($i = 1; $i<$length; $i++) {
if( $arr[$i] < $baseValue) {
//放入左邊數(shù)組
$leftArr[] = $arr[$i];
} else {
//放入右邊數(shù)組
$rightArr[] = $arr[$i];
}
}
//再分別對左邊和右邊的數(shù)組進行相同的排序處理方式遞歸調用這個函數(shù)
$leftArr = $this->quick_sort2($leftArr);
$rightArr = $this->quick_sort2($rightArr);
//合并 左邊 標尺 右邊光涂， 注意：array($baseValue),關聯(lián)著重復數(shù)據(jù)
return array_merge($leftArr, array($baseValue), $rightArr);
}
- 小結：
- 既不浪費空間又可以快一點的排序算法
- 最差時間復雜度O(N^2)，平均時間復雜度為O(NlogN)
- 推薦文章-坐在馬桶上看算法：快速排序（注：其中的算法邏輯并非標準邏輯拧烦，建議閱讀底部的評論，可做參考）
【五】.計數(shù)排序
- 思路分析
- 計數(shù)排序使用一個額外的數(shù)組C钝计，其中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)恋博。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對整數(shù)進行排序
- 算法描述：
- 找出待排序的數(shù)組中最大和最小的元素私恬；
- 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)债沮，存入數(shù)組C的第i項；
- 對所有的計數(shù)累加（從C中的第一個元素開始本鸣，每一項和前一項相加）疫衩；
- 反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1
image
- 代碼實現(xiàn)
/**
* 計數(shù)排序
* @param $arr
* @return array
*/
function countingSort($arr)
{
$len = count( $arr );
if( $len <= 1 ) return $arr;
// 找出待排序的數(shù)組中最大值和最小值
$min = min($arr);
$max = max($arr);
// 計算待排序的數(shù)組中每個元素的個數(shù)
$countArr = array();
for($i = $min; $i <= $max; $i++)
{
$countArr[$i] = 0;
}
foreach($arr as $v)
{
$countArr[$v] += 1;
}
$resArr = array();
foreach ($countArr as $k=>$c) {
for($i = 0; $i < $c; $i++)
{
$resArr[] = $k;
}
}
return $resArr;
}
- 小結：
- 計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉化為鍵存儲在額外開辟的數(shù)組空間中荣德。
作為一種線性時間復雜度的排序闷煤，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。 - 計數(shù)排序不是比較排序涮瞻，排序的速度快于任何比較排序算法
- 最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n+k) - 限制條件很多 注意
- 計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉化為鍵存儲在額外開辟的數(shù)組空間中荣德。
【六】.桶排序
- 思路分析
- 假設輸入數(shù)據(jù)服從均勻分布鲤拿，將數(shù)據(jù)分到有限數(shù)量的桶里，每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排)
- 算法描述
- 設置一個定量的數(shù)組當作空桶署咽；
- 遍歷輸入數(shù)據(jù)近顷，并且把數(shù)據(jù)一個一個放到對應的桶里去生音；
- 對每個不是空的桶進行排序；
- 從不是空的桶里把排好序的數(shù)據(jù)拼接起來窒升。
image
- 代碼實現(xiàn)
/**
* 木桶排序設計
* @param $arr 目標數(shù)組
* @param int $bucketCount 分配的木桶數(shù)目（整數(shù)）
* @return array
*/
public function bucketSort($arr,$bucketCount = 10)
{
$len = count($arr);
$max = max($arr)+1;
if ($len <= 1) {return $arr;}
//填充木桶
$arrFill = array_fill(0, $bucketCount, []);
//開始標示木桶
for($i = 0; $i < $len ; $i++)
{
$key = intval($arr[$i]/($max/$bucketCount));
array_push($arrFill[$key] , $arr[$i]);
//TODO 測試發(fā)現(xiàn)：如果此處調用缀遍，耗時翻倍
/*if(count($arrFill[$key])){
$arrFill[$key] = $this->insertSort($arrFill[$key]);
}*/
}
//對每個不是空的桶進行排序
foreach ($arrFill as $key=>$f){
if (count($f)){
$arrFill[$key] = $this->insertSort($f);
}
}
//開始從木桶中拿出數(shù)據(jù)
for($i = 0; $i < count($arrFill); $i ++)
{
if($arrFill[$i]){
for($j = 0; $j <= count($arrFill[$i]); $j++)
{ //這一行主要用來控制輸出多個數(shù)字
if ($arrFill[$i][$j]){
$arrBucket[] = $arrFill[$i][$j];
}
}
};
}
return $arrBucket;
}
-
注：
- 上述代碼是我根據(jù)對木桶排序的定義進行的設計，因為網(wǎng)上多數(shù)的PHP代碼感覺不合規(guī)范饱须，其中的
insertSort()為借用的文中所寫的插入排序 - 通過測試發(fā)現(xiàn)域醇，此方法耗時比
countingSort()要長好多，此處僅做參考不做推薦冤寿。
- 上述代碼是我根據(jù)對木桶排序的定義進行的設計，因為網(wǎng)上多數(shù)的PHP代碼感覺不合規(guī)范饱须，其中的
-
總結：
- 當輸入的元素是n 個0到k之間的整數(shù)時歹苦，它的運行時間是 O(n + k)。計數(shù)排序不是比較排序督怜，排序的速度快于任何比較排序算法殴瘦。由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序對于數(shù)據(jù)范圍很大的數(shù)組号杠，需要大量時間和內存蚪腋。
- 穩(wěn)定的排序方法
- 桶排序是計數(shù)排序的升級版
- 最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n^2)
平均情況：T(n) = O(n+k)
附錄
【1】排序算法總結
image
【2】自行分析
- 此處提供一個網(wǎng)上多數(shù)作為“桶排序”的類似代碼段,個人認為并非描述中的排序算法，倒是與文中涉及到的“計數(shù)排序”更為契合.
/**
* @param $arr 目標數(shù)組
* @return array 返回的已排序數(shù)組
*/
public function bOrCSort($arr)
{
$len = count($arr);
$max = max($arr);
if ($len <= 1) {return $arr;}
//填充木桶
$arrFill = array_fill(0, $max, 0);
for($i = 0; $i < $len ; $i++)
{
$arrFill[$arr[$i]] ++;
}
//開始從木桶中拿出數(shù)據(jù)
for($i = 0; $i <= $max; $i ++)
{
for($j = 1; $j <= $arrFill[$i]; $j++)
{ //這一行主要用來控制輸出多個數(shù)字
$arrRes[] = $i;
}
}
return $arrRes;
}
【3】用時測試
- 為了簡單比較幾種算法的用時大小姨蟋，本人隨機生成了數(shù)量為10000屉凯，數(shù)值在300以內的測試數(shù)組，文中介紹的算法用時如下：
bucketsort 用時：1013.6640071869 ms
countingSort 用時：5.6858062744141 ms
quick_sort 用時：66540.108919144 ms
selectSort 用時：15234.955072403 ms
bubbleSort 用時：162055.89604378 ms
insertSort 用時：12029.093980789 ms
內置sort 用時：3.0169486999512 ms
- 所以眼溶，簡單需求的數(shù)組排序處理還是建議使用內置的
sort()函數(shù).
