資訊專(zhuān)欄INFORMATION COLUMN
摘要：本文將介紹快速排序計(jì)數(shù)排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯(lián)合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標(biāo)志的冒泡排序種排序算法的實(shí)現(xiàn)。是一種不穩(wěn)定的排序算法。
快速排序本文將介紹快速排序、計(jì)數(shù)排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯(lián)合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標(biāo)志的冒泡排序14種排序算法的實(shí)現(xiàn)。本文是由于閱讀了文章《測(cè)試評(píng)估：14種排序算法和PHP數(shù)組》，才有想法學(xué)習(xí)、實(shí)現(xiàn)并總結(jié)這些算法，特此分享，陸續(xù)補(bǔ)充。
1、思想：主要采用了遞歸和分治的思想。選擇標(biāo)尺后，進(jìn)行遍歷數(shù)組，將大于標(biāo)尺的放到一個(gè)數(shù)組，將小于標(biāo)尺的放置到一個(gè)數(shù)組。再遞歸調(diào)用本函數(shù)并記錄結(jié)果。
2、實(shí)現(xiàn)
function quickSort($arr) {
//先判斷是否需要繼續(xù)進(jìn)行
$length = count($arr);
if($length <= 1) {return $arr;}
//選擇一個(gè)標(biāo)尺,通常選擇第一個(gè)元素
$base_num = $arr[0];
//初始化
$left = array();//小于標(biāo)尺的
$right = array();//大于標(biāo)尺的
for($i=1;$i<$length;$i++) {
if($base_num > $arr[$i]) {
$left[] = $arr[$i];
}else {
$right[] = $arr[$i];
}
}
//遞歸調(diào)用并記錄
$left = $this->quickSort($left);
$right = $this->quickSort($right);
//合并
return array_merge($left,array($base_num), $right);
3、輸入$arr = array(12, 100, 3, 20, 11,50);
4、輸出
array:6 [▼ 0 => 3 1 => 11 2 => 12 3 => 20 4 => 50 5 => 100 ]計(jì)數(shù)排序
1、此算法，是一種穩(wěn)定的線(xiàn)性時(shí)間排序算法。其基本思想是，用待排序的數(shù)作為計(jì)數(shù)數(shù)組的下標(biāo)，統(tǒng)計(jì)每個(gè)數(shù)字的個(gè)數(shù)。然后依次輸出即可得到有序序列。但是理解比較難，本人還沒(méi)理解通透，但是總結(jié)了幾個(gè)步驟：
找出數(shù)組$arr中最大的數(shù)$max
初始化用來(lái)計(jì)數(shù)的數(shù)組$count_arr，數(shù)組大小為$max
對(duì)于計(jì)數(shù)數(shù)組$count_arr鍵值等于$arr[$i]的值加1
計(jì)數(shù)數(shù)組$count_arr相鄰的兩個(gè)值相加
鍵值翻轉(zhuǎn)得到數(shù)組$over_turn
loop$over_turn，按照順序push到最終的數(shù)組$result
2、實(shí)現(xiàn)
function countingSort($arr) {
$length = count($arr);
if($length <= 1) return $arr;
$size = count($arr);
$max = $arr[0];
//找出數(shù)組中最大的數(shù)
for($i=1;$i<$size;$i++) {
if($max < $arr[$i]) $max = $arr[$i];
}
//初始化用來(lái)計(jì)數(shù)的數(shù)組
for ($i=0;$i<=$max;$i++) {
$count_arr[$i] = 0;
}
//對(duì)計(jì)數(shù)數(shù)組中鍵值等于$arr[$i]的加1
for($i=0;$i<$size;$i++) {
$count_arr[$arr[$i]]++;
}
//相鄰的兩個(gè)值相加
for($i=1;$i<=$max;$i++) {
$count_arr[$i] = $count_arr[$i-1] + $count_arr[$i];
}
//鍵與值翻轉(zhuǎn)
for ($i=$size-1;$i>=0;$i--) {
$over_turn[$count_arr[$arr[$i]]] = $arr[$i];
$count_arr[$arr[$i]]--; // 前一個(gè)數(shù)找到位置后，那么和它值相同的數(shù)位置往前一步
}
//按照順序排列
$result = array();
for ($i=1;$i<=$size;$i++) {
array_push($result,$over_turn[$i]);
}
return $result;
}
3、輸入$arr = array(8,6,1,3,4)
4、輸出
array:5 [▼ 0 => 1 1 => 3 2 => 4 3 => 6 4 => 8 ]梳排序
1、思想：梳排序同樣基于冒泡排序，梳排序比較的是固定距離處的數(shù)的比較和交換,類(lèi)似希爾那樣。是一種不穩(wěn)定的排序算法。
2、實(shí)現(xiàn)
function combSort($arr) {
$length = count($arr);
$step = (int)floor($length/1.3);
while($step >= 1) {
for($i=0;$i<$length;$i++) {
if($i+$step<$length && $arr[$i]>$arr[$i+$step]) {
$temp = $arr[$i];
$arr[$i] = $arr[$i+$step];
$arr[$i+$step] = $temp;
}
if($i+$step>$length) {
break;
}
}
$step = (int)floor($step/1.3);
}
return $arr;
}
3、輸入$arr = array(8,4,3,7,6,5,2,1)
4、輸出
array:8 [▼ 0 => 1 1 => 2 2 => 3 3 => 4 4 => 5 5 => 6 6 => 7 7 => 8 ]
待補(bǔ)充
參考文章
測(cè)試評(píng)估：14種排序算法和PHP數(shù)組：http://blog.jobbole.com/68774/
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/21682.html
摘要：計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。作為一種線(xiàn)性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。 計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。 作為一種線(xiàn)性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。 算法描述 找出待排序的數(shù)組中最大和最小的元素；...
摘要：我們現(xiàn)在來(lái)看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對(duì)二分搜索算法的改進(jìn)，插值搜索可以基于搜索的值選擇到達(dá)不同的位置。 預(yù)警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥?，所以篇幅可能較長(zhǎng)，大伙可以先Mark下來(lái)，每天抽時(shí)間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會(huì)一直更新的。 開(kāi)篇 和排序類(lèi)似，搜索或者叫做...
摘要：介紹三種排序算法快速排序選擇排序冒泡排序選擇排序選擇排序是一種簡(jiǎn)單直觀的排序算法。 介紹三種排序算法 快速排序 選擇排序 冒泡排序 選擇排序 選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法（比如序列[5， 5， 3...
摘要：在算法中，比快速排序還快的，無(wú)疑是基數(shù)排序，粗略看了一下算法，可能是基礎(chǔ)排序中的桶排序。桶排序是穩(wěn)定的桶排序是常見(jiàn)排序里最快的一種，比快排還要快大多數(shù)情況下桶排序非?？?，但是同時(shí)也非常耗空間以空間換時(shí)間 ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array....
摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個(gè)待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...
閱讀 2822·2021-11-24 09:39
閱讀 3393·2021-11-19 09:40
閱讀 2263·2021-11-17 09:33
閱讀 3753·2021-10-08 10:04
閱讀 3043·2021-09-26 09:55
閱讀 1668·2021-09-22 15:26
閱讀 931·2021-09-10 10:51
閱讀 3130·2019-08-30 15:44
