找出最大和第二大的数PHP,2020-09-01 十大经典排序算法总结php为例
排序算法說明
1 、排序的定義
對(duì)一序列對(duì)象根據(jù)某個(gè)關(guān)鍵字進(jìn)行排序。
2、術(shù)語說明
穩(wěn)定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不穩(wěn)定 ：如果a原本在b的前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面；
內(nèi)排序 ：所有排序操作都在內(nèi)存中完成；
外排序 ：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；
時(shí)間復(fù)雜度 ： 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
空間復(fù)雜度 ：運(yùn)行完一個(gè)程序所需內(nèi)存的大小。
3、常見算法總結(jié)
image.png
圖解說明
n: 數(shù)據(jù)規(guī)模
k: “桶”的個(gè)數(shù)
In-place: 占用常數(shù)內(nèi)存，不占用額外內(nèi)存
Out-place: 占用額外內(nèi)存
4、比較和非比較的區(qū)別
十種常見排序算法可以分為兩大類：
比較類排序：通過比較來決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時(shí)間比較類排序。
非比較類排序：不通過比較來決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此也稱為線性時(shí)間非比較類排序。
4.1、常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序 。
在排序的最終結(jié)果里，元素之間的次序依賴于它們之間的比較。
每個(gè)數(shù)都必須和其他數(shù)進(jìn)行比較，才能確定自己的位置 。
比較排序的優(yōu)勢是，適用于各種規(guī)模的數(shù)據(jù)，也不在乎數(shù)據(jù)的分布，都能進(jìn)行排序。可以說，比較排序適用于一切需要排序的情況。
在冒泡排序之類的排序中，問題規(guī)模為n，又因?yàn)樾枰容^n次，所以平均時(shí)間復(fù)雜度為O(n2)。在歸并排序、快速排序之類的排序中，問題規(guī)模通過分治法消減為logN次，所以時(shí)間復(fù)雜度平均O(nlogn)。
4.2、計(jì)數(shù)排序、基數(shù)排序、桶排序則屬于非比較排序 。
非比較排序只要確定每個(gè)元素之前的已有的元素個(gè)數(shù)即可，所以一次遍歷即可解決。算法時(shí)間復(fù)雜度O(n)。
非比較排序時(shí)間復(fù)雜度低，但由于非比較排序需要占用空間來確定唯一位置。所以對(duì)數(shù)據(jù)規(guī)模和數(shù)據(jù)分布有一定的要求。
非比較排序是通過確定每個(gè)元素之前，應(yīng)該有多少個(gè)元素來排序。針對(duì)數(shù)組arr，計(jì)算arr[i]之前有多少個(gè)元素，則唯一確定了arr[i]在排序后數(shù)組中的位置 。
image.png
5、各個(gè)排序法詳解
5.1、冒泡排序(Bubble Sort)
冒泡排序是一種簡單的排序算法。
算法重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。
走訪數(shù)列的工作重復(fù)地進(jìn)行，直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
因?yàn)榕判蜻^程讓 較大的數(shù)往下沉，較小的往上冒，故而叫冒泡法。
5.1.1 算法描述
1、從第一個(gè)元素開始，比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2、從開始第一對(duì)到結(jié)尾的最后一對(duì)，對(duì)每一對(duì)相鄰元素作同樣的工作。比較結(jié)束后，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3、對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4、重復(fù)上面的步驟，每次比較的對(duì)數(shù)會(huì)越來越少，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
5.1.2 冒泡排序動(dòng)圖演示
0.gif
5.1.3 示例代碼
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
function bubbleSort($arr){
$length = count($arr);
for ($i = 0; $i
for ($j = $i+1; $j < $length; $j++) { // 第二層為從$i+1的地方循環(huán)到數(shù)組最后
if ($arr[$i] > $arr[$j]) { // 比較數(shù)組中兩個(gè)相鄰值的大小
$tem = $arr[$i]; // 這里臨時(shí)變量，存貯$i的值
$arr[$i] = $arr[$j]; // 第一次更換位置
$arr[$j] = $tem; // 完成位置互換
}
}
}
return $arr;
}
print_r(bubbleSort($arr));
5.1.4算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
5.2.選擇排序(Selection Sort)
表現(xiàn)最穩(wěn)定的排序算法之一(這個(gè)穩(wěn)定不是指算法層面上的穩(wěn)定哈，相信聰明的你能明白我說的意思2333)，因?yàn)闊o論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度.....所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧。
5.2.1算法簡介
選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小(大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
5.2.2算法描述和實(shí)現(xiàn)
n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
<1>.初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
<2>.第i趟排序(i=1,2,3...n-1)開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n)。該趟排序從當(dāng)前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)；
<3>.n-1趟結(jié)束，數(shù)組有序化了。
5.2.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
function SelectionSort($arr)
{
$length = count($arr);
for ($i = 0; $i < $length - 1; $i++) { // $i為已經(jīng)排序序列的末尾下標(biāo)
$min = $i; // 暫存未排列序列的最小值下標(biāo)
for ($j = $i + 1; $j < $length; $j++) { // 遍歷未排列序列
if ($arr[$j] < $arr[$min]) { // 找出排列序列最小值，下標(biāo)賦給$min
$min = $j;
}
}
if ($min != $i) { // 如果找到最小值，放到已排列序列末尾
$t = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $t;
}
}
return $arr;
}
print_r(SelectionSort($arr));
5.2.4、選擇排序動(dòng)圖演示：
1.gif
5.2.5 算法分析
最佳情況：T(n) = O(n2)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
5.3 、插入排序(Insertion Sort)
插入排序的代碼實(shí)現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^撲克牌的人都應(yīng)該能夠秒懂。當(dāng)然，如果你說你打撲克牌摸牌的時(shí)候從來不按牌的大小整理牌，那估計(jì)這輩子你對(duì)插入排序的算法都不會(huì)產(chǎn)生任何興趣了.....
5.3.1、算法簡介
插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序(即只需用到O(1)的額外空間的排序)，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
5.3.2、算法描述和實(shí)現(xiàn)
一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
<1>.從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；
<2>.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
<3>.如果該元素(已排序)大于新元素，將該元素移到下一位置；
<4>.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
<5>.將新元素插入到該位置后；
<6>.重復(fù)步驟2~5。
5.3.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
//插入排序
function insert_sort($arr) {
//獲取數(shù)組單元個(gè)數(shù)
$count = count($arr);
//外層循環(huán)用于從未排序區(qū)域中取出待排序元素
for ($i=1; $i < $count; $i++) {
//獲取當(dāng)前需要插入已排序區(qū)域的元素值
$temp = $arr[$i];
//內(nèi)層循環(huán)用于從已排序區(qū)域?qū)ふ掖判蛟氐牟迦胛恢?/p>
for ($j=$i-1; $j >= 0; $j--) {
//如果$arr[$i]比已排序區(qū)域的$arr[$j]小，就后移$arr[$j]
if ($temp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $temp;
} else {
//如果$arr[$i]不小于$arr[$j]，則對(duì)已排序區(qū)無需再排序
break;
}
}
}
return $arr;
}
print_r(insert_sort($arr));
5.3.4、動(dòng)圖演示:
000.gif
5.3.5 算法分析
最佳情況：T(n) = O(n)
最壞情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
5.4希爾排序(Shell Sort)
5.4.1、算法簡介
希爾排序是希爾(Donald Shell) 于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序，同時(shí)該算法是沖破O(n2)的第一批算法之一。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
希爾排序是把記錄按下表的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
5.4.2、算法描述和實(shí)現(xiàn)
我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續(xù)以gap = gap/2的方式，這種增量選擇我們可以用一個(gè)序列來表示，{n/2,(n/2)/2…1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個(gè)數(shù)學(xué)難題，我們選擇的這個(gè)增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實(shí)這個(gè)增量序列不是最優(yōu)的。此處我們做示例使用希爾增量。
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
步驟1：選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
步驟2：按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
步驟3：每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。
5.4.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
//希爾排序(對(duì)直接插入排序的改進(jìn))
function ShellSort(array $arr)
{
$len = count($arr); // 將$arr按升序排列
$f = 3; // 定義因子
$h = 1; // 最小為1
while ($h < $len/$f){
$h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
}
while ($h >= 1){ // 將數(shù)組變?yōu)閔有序
for ($i = $h; $i < $len; $i++){ // 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的關(guān)鍵
for ($j = $i; $j >= $h; $j -= $h){
if ($arr[$j] < $arr[$j-$h]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-$h];
$arr[$j-$h] = $temp;
}
//print_r($arr);echo '
'; // 打開這行注釋，可以看到每一步被替換的情形
}
}
$h = intval($h/$f);
}
return $arr;
}
print_r(ShellSort($arr));
5.4.4、動(dòng)圖演示:
2.gif
5.4.5 算法分析
最佳情況：T(n) = O(nlog2 n)
最壞情況：T(n) = O(nlog2 n)
平均情況：T(n) =O(nlog2n)
5.5、歸并排序(Merge Sort)
5.5.1、算法簡介
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(n log n)的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
歸并排序 是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
5.5.2、算法描述和實(shí)現(xiàn)
1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；
2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3、比較兩個(gè)指針?biāo)赶虻脑?#xff0c;選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4、重復(fù)步驟3直到某一指針達(dá)到序列尾
5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾
5.5.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
// 歸并排序
/**
*遞歸拆分，直到剩下一個(gè)元素，我們認(rèn)為他是有序的
*/
function merge_sort(array $lists)
{
$n = count($lists);
if ($n <= 1) {
return $lists;
}
$left = merge_sort(array_slice($lists, 0, floor($n / 2)));
$right = merge_sort(array_slice($lists, floor($n / 2)));
$lists = merge($left, $right);
return $lists;
}
/**
*兩兩循環(huán)比較，當(dāng)左邊的第一個(gè)元素小于右邊的第一個(gè)元素，將左邊第一個(gè)元素放入臨時(shí)數(shù)組
*然后拿左邊數(shù)組的第二個(gè)元素與右邊數(shù)組的第一個(gè)元素比較，如果左邊第二個(gè)元素大于右邊第一個(gè)元素，將
*右邊第一個(gè)放入臨時(shí)數(shù)組
*依次比較，知道有一邊的元素取完為止
*/
function merge(array $left, array $right)
{
$lists = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$lists[] = $left[$i];
$i++;
} else {
$lists[] = $right[$j];
$j++;
}
}
$lists = array_merge($lists, array_slice($left, $i));
$lists = array_merge($lists, array_slice($right, $j));
return $lists;
}
print_r(merge_sort($arr));
5.5.4、動(dòng)圖演示:
3.gif
3.gif
5.5.5 算法分析
最佳情況：T(n) = O(n)
最差情況：T(n) = O(nlogn)
平均情況：T(n) = O(nlogn)
5.6、快速排序(Quick Sort)
5.6.1、算法簡介
快速排序 的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。
5.6.2、算法描述和實(shí)現(xiàn)
快速排序使用分治法來把一個(gè)串(list)分為兩個(gè)子串(sub-lists)。具體算法描述如下：
1、從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”(pivot)；
2、重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的
數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作；
3、遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
5.6.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
//快速排序
function quick_sort(array $arr)
{
// 判斷是否需要運(yùn)行，因下面已拿出一個(gè)中間值，這里<=1
if (count($arr) <= 1) {
return $arr;
}
$middle = $arr[0]; // 中間值
//簡寫法 $left = $right = array();
$left = array(); // 以基準(zhǔn)值為分界線，小于基準(zhǔn)值的放在左側(cè)
$right = array();// 以基準(zhǔn)值為分界線，大于基準(zhǔn)值的放在右側(cè)
// 循環(huán)比較
for ($i=1; $i < count($arr); $i++) {
if ($middle < $arr[$i]) {
$right[] = $arr[$i]; // 大于中間值
} else {
$left[] = $arr[$i]; // 小于中間值
}
}
// 遞歸排序劃分好的2邊
$left = quick_sort($left);
$right = quick_sort($right);
// 合并排序后的數(shù)據(jù)，別忘了合并中間值
return array_merge($left, array($middle), $right);
}
print_r(quick_sort($arr));
5.6.4、動(dòng)圖演示:
4.gif
5.6.5 算法分析
最佳情況：T(n) = O(nlogn)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(nlogn)
5.7、堆排序(Heap Sort)
5.7.1、算法簡介
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。
5.7.2、算法描述和實(shí)現(xiàn)
1、創(chuàng)建一個(gè)堆H[0..n-1]；
2、把堆首(最大值)和堆尾互換；
3、把堆的尺寸縮小1，并調(diào)用shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；
4、 重復(fù)步驟2，直到堆的尺寸為1。
5.7.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
//堆排序(對(duì)簡單選擇排序的改進(jìn))
/**
* 使用異或交換2個(gè)值，原理：一個(gè)值經(jīng)過同一個(gè)值的2次異或后，原值不變
* @param int $a
* @param int $b
*/
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
/**
* 整理當(dāng)前樹節(jié)點(diǎn)($n)，臨界點(diǎn)$last之后為已排序好的元素
* 調(diào)整 $arr[$start]的關(guān)鍵字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成為一個(gè)大根堆(根節(jié)點(diǎn)最大的完全二叉樹)
* 注意這里節(jié)點(diǎn) s 的左右子集是 2*s + 1 和 2*s+2 (數(shù)組開始下標(biāo)為 0 時(shí))
* @param int $n
* @param int $last
* @param array $arr
*
*/
function HeapAdjust(array &$arr,$start,$end){
$temp = $arr[$start];
//沿關(guān)鍵字較大的子集節(jié)點(diǎn)向下篩選
//左右子集計(jì)算(我這里數(shù)組開始下標(biāo)識(shí) 0)
//左子集2 * $start + 1，右子集2 * $start + 2
for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
if($j != $end && $arr[$j] < $arr[$j + 1]){
$j ++; //轉(zhuǎn)化為右子集
}
if($temp >= $arr[$j]){
break; //已經(jīng)滿足大根堆
}
//將根節(jié)點(diǎn)設(shè)置為子節(jié)點(diǎn)的較大值
$arr[$start] = $arr[$j];
//繼續(xù)往下
$start = $j;
}
$arr[$start] = $temp;
}
/**
* 堆排序(最大堆)
* @param array $arr
*/
function HeapSort(array &$arr){
$count = count($arr);
//先將數(shù)組構(gòu)造成大根堆(由于是完全二叉樹，所以這里用floor($count/2)-1，下標(biāo)小于或等于這數(shù)的節(jié)點(diǎn)都是有子集的節(jié)點(diǎn))
for($i = floor($count / 2) - 1;$i >= 0;$i --){
HeapAdjust($arr,$i,$count);
}
for($i = $count - 1;$i >= 0;$i --){
//將堆頂元素與最后一個(gè)元素交換，獲取到最大元素(交換后的最后一個(gè)元素)，將最大元素放到數(shù)組末尾
swap($arr,0,$i);
//經(jīng)過交換，將最后一個(gè)元素(最大元素)脫離大根堆，并將未經(jīng)排序的新樹($arr[0...$i-1])重新調(diào)整為大根堆
HeapAdjust($arr,0,$i - 1);
}
}
HeapSort($arr);
print_r($arr);
5.7.4、動(dòng)圖演示:
5、.gif
5.7.5 算法分析
最佳情況：T(n) = O(nlogn)
最差情況：T(n) = O(nlogn)
平均情況：T(n) = O(nlogn)
5.8、計(jì)數(shù)排序(Counting Sort)
5.8.1、算法簡介
計(jì)數(shù)排序 的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。 作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
計(jì)數(shù)排序(Counting sort) 是一種穩(wěn)定的排序算法。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對(duì)整數(shù)進(jìn)行排序。
5.8.2、算法描述和實(shí)現(xiàn)
1、找出待排序的數(shù)組中最大和最小的元素；
2、統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；
3、對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加)；
4、反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1。
5.8.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
/**
* 計(jì)數(shù)排序: 桶排序的一種
*/
function counting_sort($arr)
{
$min = min($arr);
$max = max($arr);
$count = array();
for($i = $min; $i <= $max; $i++)
{
$count[$i] = 0;
}
foreach($arr as $number)
{
$count[$number]++;
}
$z = 0;
for($i = $min; $i <= $max; $i++) {
while( $count[$i]-- > 0 ) {
$arr[$z++] = $i;
}
}
return $arr;
}
print_r(counting_sort($arr));
5.8.4、動(dòng)圖演示:
6.gif
5.8.5 算法分析
當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 O(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的最大值與最小值的差加上1)，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。
最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n+k)
5.9、桶排序(Bucket Sort)
5.9.1、算法簡介
桶排序 是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
桶排序 (Bucket sort)的工作的原理：
假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排
5.9.2、算法描述和實(shí)現(xiàn)
1、設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
2、遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
3、對(duì)每個(gè)不是空的桶進(jìn)行排序；
4、從不是空的桶里把排好序的數(shù)據(jù)拼接起來。
5.9.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
/**
* 桶排序的辦法，每個(gè)桶存儲(chǔ)相同值的數(shù)據(jù)
* */
function bucketSort($nonSortArray){
//選出桶中最大值和最小值
$min = min($nonSortArray);
$max = max($nonSortArray);
//生成桶,默認(rèn)每個(gè)桶中數(shù)據(jù)只有0個(gè)
$bucket = array_fill($min, $max-$min+1, 0);
//數(shù)據(jù)入桶
foreach ($nonSortArray as $value){
$bucket[$value]++;//對(duì)應(yīng)桶的個(gè)數(shù)計(jì)增
}
//數(shù)據(jù)出桶
$sortArray = array();
foreach ($bucket as $k=>$v){
for($i=1;$i<=$v;$i++){
//每個(gè)桶中的數(shù)據(jù)個(gè)數(shù)
$sortArray[]=$k;
}
}
return $sortArray;
}
print_r(bucketSort($arr));
5.9.4、動(dòng)圖演示:
5.png
5.9.5 算法分析
可以看出時(shí)間復(fù)雜度還是蠻高的，因?yàn)橐炎钚≈岛妥畲笾抵g的數(shù)據(jù)都要生成數(shù)組，所以適合數(shù)據(jù)密集度比較高的，極差比較小的，而且只能用于整數(shù)排序，可見這個(gè)應(yīng)用范圍還是挺小的；
說的官方一點(diǎn)就是：
1)待排序列的值處于一個(gè)可枚舉的范圍內(nèi)
2)待排序列所在可枚舉范圍不應(yīng)太大，不然開銷會(huì)很大
最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n2)
5.10、
5.10.1、算法簡介
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串(比如名字或日期)和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。
5.10.2、算法描述和實(shí)現(xiàn)
1、取得數(shù)組中的最大數(shù)，并取得位數(shù)；
2、arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
3、對(duì)radix進(jìn)行計(jì)數(shù)排序(利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn))；
5.10.3、代碼實(shí)現(xiàn):
$arr = array(23,15,43,25,54,2,6,82,11,5,21,32,65,51,66,21,59,42,95,33,72,15,61);
/**
* 基數(shù)排序
*
* @param array $lists
* @return array
*/
function radix_sort(array $lists)
{
$radix = 10;
$max = max($lists);
$k = ceil(log($max, $radix));
if ($max == pow($radix, $k)) {
$k++;
}
for ($i = 1; $i <= $k; $i++) {
$newLists = array_fill(0, $radix, []);
for ($j = 0; $j < count($lists); $j++) {
$key = $lists[$j] / pow($radix, $i - 1) % $radix;
$newLists[$key][] = $lists[$j];
}
$lists = [];
for ($j = 0; $j < $radix; $j++) {
$lists = array_merge($lists, $newLists[$j]);
}
}
return $lists;
}
print_r(radix_sort($arr));
5.10.4、動(dòng)圖演示:
7.gif
5.10.5、 算法分析
最佳情況：T(n) = O(n * k)
最差情況：T(n) = O(n * k)
平均情況：T(n) = O(n * k)
5.10.6、基數(shù)排序有兩種方法：
MSD 從高位開始進(jìn)行排序
LSD 從低位開始進(jìn)行排序
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序： 根據(jù)鍵值的每位數(shù)字來分配桶
計(jì)數(shù)排序： 每個(gè)桶只存儲(chǔ)單一鍵值
桶排序： 每個(gè)桶存儲(chǔ)一定范圍的數(shù)值
20180808234300816.png
d 表示位數(shù)，
k 在基數(shù)排序中表示 k 進(jìn)制，
在桶排序中表示桶的個(gè)數(shù)， maxV 和 minV 表示元素最大值和最小值。
首先，基數(shù)排序和計(jì)數(shù)排序都可以看作是桶排序。
計(jì)數(shù)排序本質(zhì)上是一種特殊的桶排序，當(dāng)桶的個(gè)數(shù)取最大( maxV-minV+1 )的時(shí)候，就變成了計(jì)數(shù)排序。
基數(shù)排序也是一種桶排序。
桶排序是按值區(qū)間劃分桶，基數(shù)排序是按數(shù)位來劃分；基數(shù)排序可以看做是多輪桶排序，每個(gè)數(shù)位上都進(jìn)行一輪桶排序。
當(dāng)用最大值作為基數(shù)時(shí)，基數(shù)排序就退化成了計(jì)數(shù)排序。
當(dāng)使用2進(jìn)制時(shí)， k=2 最小，位數(shù) d 最大，時(shí)間復(fù)雜度 O(nd) 會(huì)變大，空間復(fù)雜度 O(n+k) 會(huì)變小。當(dāng)用最大
值作為基數(shù)時(shí)， k=maxV 最大， d=1 最小，此時(shí)時(shí)間復(fù)雜度 O(nd) 變小，但是空間復(fù)雜度 O(n+k) 會(huì)急劇增大，此時(shí)基數(shù)排序退化成了計(jì)數(shù)排序。
總結(jié)
以上是生活随笔為你收集整理的找出最大和第二大的数PHP,2020-09-01 十大经典排序算法总结php为例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php fastcgi_param,ng
- 下一篇： php 类 静态调用 实例化 效率,ph