常見的排序算法：
- 快速排序漓骚、堆排序蝌衔、歸并排序、選擇排序
- 插入排序蝌蹂、二分插入排序
- 冒泡排序噩斟、雞尾酒排序
- 桶排序、計(jì)數(shù)排序孤个、基數(shù)排序亩冬、位圖排序
技能點(diǎn)：
1.歸并排序在O(N*logN)的幾種排序方法（快速排序，歸并排序，希爾排序硅急，堆排序）效率比較高覆享。
2.位圖排序、計(jì)數(shù)排序 不是比較排序营袜，通過空間消耗撒顿，實(shí)現(xiàn)時(shí)間復(fù)雜度O(n)的排序。
快速排序
通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的A荚板、B兩部分凤壁，A部分全部小于基準(zhǔn)值，B部分全部大于基準(zhǔn)值跪另。然后在對(duì)兩部分做相同的處理拧抖，已完成排序的功能。
算法描述與分析
- 從數(shù)列中挑選一個(gè)元素免绿，作為基準(zhǔn)值唧席， pivot;
- 便利排序數(shù)列，比基準(zhǔn)值小的放在左邊A嘲驾，大的放在右邊B（相同的放在任意一邊）淌哟。待分組完成后基準(zhǔn)值就處于A、B的中間位置辽故。 這個(gè)過程稱為分區(qū)(partition)操作徒仓，兩種實(shí)現(xiàn)方式具體實(shí)現(xiàn)見代碼
-
遞歸排序A、B兩部分誊垢，重復(fù)上面1 2兩步掉弛，進(jìn)行排序。
快速排序-圖例
復(fù)雜度
時(shí)間復(fù)雜度:
A. o(nlogn)* : 將數(shù)組分解為一些列小問題進(jìn)行獨(dú)立解決喂走，上述的過程重復(fù)logn次得到有序的序列狰晚； 每次都需要對(duì)n個(gè)進(jìn)行一次處理，所以時(shí)間復(fù)雜度為 n*logn
B. o(n^2）: 固定選擇第一個(gè)元素做基準(zhǔn)值缴啡，對(duì)倒序數(shù)組進(jìn)行正序排列；每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列瓷们，每次只排一個(gè)业栅。相當(dāng)于向后冒泡排序，所以時(shí)間復(fù)雜度為o(n^2)
空間復(fù)雜度：
額外使用的空間需要看具體的代碼實(shí)現(xiàn)谬晕，理論上最優(yōu)情況下空間復(fù)雜度為o(1)碘裕，只是用一個(gè)交換空間； 如果考慮遞歸的實(shí)現(xiàn)邏輯則復(fù)雜度為 o(logn) 攒钳。
代碼實(shí)現(xiàn)
教科書式實(shí)現(xiàn)：
//普通方法實(shí)現(xiàn)
function quick_sort( &$arr, $left, $right ){
if( $left < $right){
//取基準(zhǔn)值帮孔，取最左邊的一個(gè)元素
$pivot = $arr[$left];
//隨機(jī)取基準(zhǔn)值 - 避免對(duì)倒序數(shù)組進(jìn)行正序排序時(shí)，時(shí)間復(fù)雜度 O(n^2)的情況
// $k = rand($left, $right);
// swap($arr, $left, $k);
// $pivot = $arr[$left];
$i = $left; $j = $right;
//一趟排序比較
while($i < $j){
//基準(zhǔn)值從左邊選取的，所以先從右側(cè)開始比較文兢；反之亦然晤斩。(注)
while( $arr[$j] >= $pivot && $j > $i){
$j--;
}
swap($arr, $i, $j);
while( $arr[$i] < $pivot && $i < $j ){
$i++;
}
swap($arr, $i, $j);
}
quick_sort($arr, $left, $i-1); //對(duì)左邊內(nèi)容進(jìn)行排序
quick_sort($arr, $i+1, $right); //右邊內(nèi)容進(jìn)行排序
}
}
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
quick_sort($arr, 0, count($arr)-1 );
echo implode(',', $arr);
劍指offer的實(shí)現(xiàn)：
//分區(qū)方法. 這個(gè)思想很重要，可以在多個(gè)問題中使用姆坚。如：取前幾名澳泵、字符串大小寫字母分組等
function partition(&$arr, $left, $right){
//隨機(jī)、取最后一個(gè)為基準(zhǔn)值兼呵，方便從頭開始遍歷
$k = rand($left, $right);
swap($arr, $k, $right);
$pivot = $arr[$right];
// 取兩個(gè)指針A B兔辅，從{$left}開始走，B在遇到小于基準(zhǔn)值是前走击喂；
// 當(dāng)A遇到小于基準(zhǔn)值時(shí)和B處交換值维苔；然后B指針前移一位。
// 完成一遍遍歷懂昂，B指針的位置就是分割位介时。在把基準(zhǔn)值替換到B+1即可
$b = $left-1;
for($a=$left; $a<=$right; $a++){
if( $arr[$a] < $pivot){
$b++;
if( $a != $b){
swap($arr, $a, $b);
}
}
}
$b++; //指針后移一位，然后替換基準(zhǔn)值忍法，保證前面的都小潮尝、后面的都大
swap($arr, $b, $right);
return $b;
}
//交換元素。除了這種方式還可以使用：
// a=a+b; b=a-b ; a=a-b饿序，加法來實(shí)現(xiàn)勉失，不申請(qǐng)額外空間
// a=a^b; b = a^b; a = b^a，異或來實(shí)現(xiàn)
function swap(&$arr, $i, $j){
$t = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $t;
}
//排序
function quick_sort( &$arr, $left, $right ){
if( $left < $right){
$index = partition($arr, $left, $right);
quick_sort($arr, $left, $index-1);
quick_sort($arr, $index+1, $right);
}
}
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
quick_sort($arr, 0, count($arr)-1 );
echo implode(',', $arr);
運(yùn)行耗時(shí)出現(xiàn)兩種情況：
A: 13,27,38,49,50,65,76,97[Finished in 0.2s]
B: 13,27,38,49,50,65,76,97[Finished in 0.1s]
原因：排序使用了隨機(jī)基準(zhǔn)值的方法原探，所以分區(qū)比較乱凿、分區(qū)大小都是隨機(jī)的。所以遞歸次數(shù)會(huì)有不同咽弦，耗時(shí)自然也就不同徒蟆。
堆排序
利用堆這種數(shù)據(jù)結(jié)構(gòu)，堆積生成一個(gè)近似完全的二叉樹型型，并且滿足堆積性質(zhì)：即子節(jié)點(diǎn)的建值總是小于(或大于)它的父節(jié)點(diǎn)段审。 二叉樹使用數(shù)組來實(shí)現(xiàn)，從頭到尾對(duì)應(yīng)堆的從上到下闹蒜。
示例
最大堆（父節(jié)點(diǎn)大于任何一個(gè)子節(jié)點(diǎn)）寺枉，則根節(jié)點(diǎn)時(shí)最大值。將根節(jié)點(diǎn)取出來绷落，剩下的進(jìn)行堆調(diào)整生成最大堆姥闪；重復(fù)上述步驟，直到堆無節(jié)點(diǎn)時(shí)完成排序砌烁。
海量數(shù)據(jù)TopK問題
用堆排序來解決海量數(shù)據(jù)TopK 問題會(huì)非常好筐喳。構(gòu)建K個(gè)節(jié)點(diǎn)的最小堆；遍歷數(shù)據(jù)，當(dāng)數(shù)據(jù)大于最小根節(jié)點(diǎn)時(shí)替換根節(jié)點(diǎn)避归，進(jìn)行堆調(diào)整荣月，生成最小堆；遍歷結(jié)束時(shí)槐脏，堆會(huì)保存其中最大的K個(gè)元素喉童； 在進(jìn)行堆排序，生成K個(gè)元素從大到小的排列顿天。
算法描述與分析：
我們這里先介紹幾個(gè)問題堂氯，一步步推到堆排序。
什么是堆
定義上面已有說明牌废，示例如下：
使用數(shù)組存儲(chǔ)：$arr = [1, 2, 3, 17, 19, 36, 7, 15, 170]
堆調(diào)整
為了保證堆的特性而做的一個(gè)操作咽白。將該根節(jié)點(diǎn)就行下沉操作，一直沉到合適的位置鸟缕，使得剛才的子樹滿足堆的性質(zhì)晶框。
例如對(duì)最大堆進(jìn)行堆調(diào)整：
1.對(duì)應(yīng)的數(shù)組元素A[i], 左孩子 left(2i+1), 右孩子right(2i+2), 中找最大的那一個(gè)，將其下標(biāo)存入largest中懂从；
2.如果A[i] 是最大的元素授段，則程序直接結(jié)束；
3.否則番甩，i的某個(gè)子節(jié)點(diǎn)為最大元素侵贵，將A[i] 與 A[largest] 交換；
4.在從交換的子子節(jié)點(diǎn)開始缘薛，重復(fù)1,2,3步窍育，直到葉子節(jié)點(diǎn)，完成一次堆調(diào)整宴胧。
建堆
建堆就是一個(gè)不斷進(jìn)行堆調(diào)整的過程漱抓。在數(shù)組中，我們一般從第n/2個(gè)數(shù)開始做堆調(diào)整恕齐，一直到下標(biāo)為0的數(shù) (因?yàn)橄聵?biāo)大于n/2的數(shù)乞娄，都是葉子節(jié)點(diǎn)，無子數(shù)显歧，所以其子數(shù)已經(jīng)滿足堆的性質(zhì)了)仪或。
堆調(diào)整只判斷節(jié)點(diǎn)子樹，進(jìn)行該節(jié)點(diǎn)下沉操作追迟，并不和父節(jié)點(diǎn)進(jìn)行比較，
所以建堆時(shí)必須從后向前進(jìn)行骚腥，首先保證子樹滿足特性敦间，在一步步往上推。
ps: 數(shù)組下標(biāo)從0開始，建堆節(jié)點(diǎn)應(yīng)從下標(biāo) n/2 -1 開始
堆排序
堆排序是在建堆完成之后廓块，進(jìn)行的操作厢绝。
以最大堆為例，堆以數(shù)組形式進(jìn)行存儲(chǔ)带猴，所以A[0]是最大值昔汉，將A[0]與A[n-1]交換，然后對(duì)A[0n-2]進(jìn)行堆調(diào)整拴清。第二次將A[0]與A[n-2]進(jìn)行交換靶病，A[0n-3]進(jìn)行堆調(diào)整，重復(fù)這樣的操作直到A[0]與A[1]進(jìn)行交換口予。 每次都將最大的數(shù)移入后面的區(qū)間娄周，故操作完成之后，所得的數(shù)組就是從小到大有序排列的了沪停。
堆排序圖解
復(fù)雜度
時(shí)間復(fù)雜度：
O(nlogn)* : 建堆過程為O(n), 堆調(diào)整過程為O(nlogn)
空間復(fù)雜度：
O(1) : 就地排序
代碼實(shí)現(xiàn)
<?php
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
sortHeap($arr);
function sortHeap(&$arr){
$heap_size = count($arr) - 1;
createHeap($arr, $heap_size );
echo '建堆結(jié)果：'.implode(',', $arr)."\r\n";
heapPrint($arr, $heap_size);
//堆排序
$n = $heap_size;
for($i=0; $i<=$n; $i++ ){
swap($arr, 0, $heap_size); //最大值替換到最后面
$heap_size--;
adjustHeap($arr, $heap_size, 0); //A[0]替換為新的值煤辨，從該節(jié)點(diǎn)進(jìn)行堆調(diào)整
}
echo '堆排序結(jié)果'.implode(',', $arr)."\r\n";
}
//建堆
function createHeap( &$arr, $heap_size){
$n = floor($heap_size/2) -1;
for($i=$n; $i>=0; $i-- ){
// 從最后一個(gè)非葉子節(jié)點(diǎn)開始，下標(biāo)遞減進(jìn)行建堆木张。
// 保證節(jié)點(diǎn)的子樹滿足堆的性質(zhì)众辨，才能進(jìn)一步對(duì)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行堆調(diào)整; 否則會(huì)有問題
adjustHeap($arr, $heap_size, $i);
}
}
//堆調(diào)整 - 最大堆特性
function adjustHeap( &$arr, $heap_size, $i){
$left = 2*$i + 1; //左子節(jié)點(diǎn)
$right = 2*$i + 2; //右子節(jié)點(diǎn)
$largest = $i; //默認(rèn)最大節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
while( $left < $heap_size || $right<$heap_size){
if( $left < $heap_size && $arr[$left] > $arr[$largest] ){
$largest = $left; //左子節(jié)點(diǎn)大于目前值最大節(jié)點(diǎn)
}
if( $right<$heap_size && $arr[$right] > $arr[$largest] ){
$largest = $right; //右子節(jié)點(diǎn)大于最大節(jié)點(diǎn)
}
//子節(jié)點(diǎn)大于該節(jié)點(diǎn)，需要將該節(jié)點(diǎn)下沉舷礼，并對(duì)下沉后的節(jié)點(diǎn)進(jìn)行子樹堆調(diào)整
if($largest != $i){
swap($arr, $largest, $i);
$i = $largest;
$left = 2*$i+1;
$right = 2*$i+2;
}else{
// 該節(jié)點(diǎn)值是最大值時(shí)鹃彻，結(jié)束調(diào)整。
// 因?yàn)椋荷顚哟蔚淖訕湓诮ǘ褧r(shí)已經(jīng)滿足堆性質(zhì)且轨，不需要再進(jìn)行判斷
break;
}
}
}
function swap(&$arr, $i, $j){
$t = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $t;
}
//堆打印
function heapPrint($arr, $heap_size){
//判斷有多少行
$rows = 1;
while( pow(2, $rows-1) < $heap_size ){ $rows++;}
//最后一行葉子節(jié)點(diǎn)的個(gè)數(shù)浮声，最大個(gè)數(shù)
$lastNumbers = pow(2, $rows-1);
//輸出
$row = 1;
$num = pow(2, $row-1);
for( $i=0; $i<$heap_size; $i++){
$t = $lastNumbers/ ( pow(2, $row-1) +1 ); //空格平均分割。除以（數(shù)字個(gè)數(shù)+1）
$t = ceil($t);
for($j=0; $j<$t; $j++){ echo " " ; }
echo $arr[$i];
if( $i+1 == $num ){
echo "\r\n";
$row++;
$num += pow(2, $row-1);
}
}
echo "\r\n";
}
運(yùn)行結(jié)果：
建堆結(jié)果：97,76,65,38,49,13,27,50
97
76 65
38 49 13 27
堆排序結(jié)果: 13,27,38,49,50,65,76,97
[Finished in 0.2s]
歸并排序
歸并排序是 分治法(Divide and Conquer)的一個(gè)非常經(jīng)典的應(yīng)用旋奢。將大序列拆分成n個(gè)小序列泳挥，先使小序列有序，然后合并有序子序列至朗，得到排序結(jié)果屉符。
將兩個(gè)有序序列合并成一個(gè)序列的方法叫做2路歸并。
算法描述與分析：
遞歸方法實(shí)現(xiàn)：
1.Divide: 把長(zhǎng)度為n的序列分成長(zhǎng)度為 n/2的子序列锹引；
2.Conquer: 對(duì)每個(gè)子序列采用歸并排序矗钟；
3.Combine：將排序好的兩個(gè)子序列合并成最終的排序序列。
歸并操作的工作原理如下：
第一步：申請(qǐng)空間嫌变，使其大小為兩個(gè)已經(jīng)排序序列之和吨艇，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間腾啥，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾东涡。
復(fù)雜度：
時(shí)間復(fù)雜度：
O(nlogn): 將序列分成小序列需要logn步冯吓，每一步合并都需要對(duì)n個(gè)元素進(jìn)行比較，時(shí)間復(fù)雜度為O(n)疮跑，故一共為 o(nlogn)
空間復(fù)雜度:
O(n)
代碼實(shí)現(xiàn)：
function mergeSort($arr){
$len = count($arr);
if($len<=1) return $arr;
$mid = intval($len/2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
$a = mergeSort($left); //拆分排序子序列
$b = mergeSort($right); //
$arr = merge($a, $b); //合并组贺，拆分幾次，就合并幾次
return $arr;
}
//2路合并
function merge($arrA, $arrB){
$arrC = [];
while ( count($arrA)>0 && count($arrB)>0 ) {
$arrC[] = ($arrA[0] < $arrB[0]) ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
$arr = [49, 38, 65, 97, 76, 13, 27, 50];
$arr = mergeSort($arr);
echo implode(',', $arr);
輸出結(jié)果：13,27,38,49,50,65,76,97[Finished in 0.2s]
插入排序
簡(jiǎn)介：
構(gòu)建有序序列祖娘，對(duì)于未排序數(shù)據(jù)失尖，在已排序序列從后向前掃描，找到合適的位置K并插入渐苏。 位置K之后的元素需要全部后移掀潮。
算法描述與分析：
- 取第一個(gè)元素構(gòu)建有序序列；
- 取出下一個(gè)元素B整以，對(duì)有序序列從后向前掃描胧辽； 如果掃描到的元素大于B,則后移該元素；否則將B插入該元素后面公黑；
- 重復(fù)第2步邑商，直到遍歷完所有數(shù)據(jù)。
復(fù)雜度：
時(shí)間：O(n^2)
空間：O(1)
代碼實(shí)現(xiàn)：
function insert_sort($arr){
for( $i =1; $i<count($arr); $i++){
$t = $arr[$i]; //待排元素
for($j=$i-1; $j>=0; $j--){
if( $arr[$j] > $t ){
$arr[$j+1] = $arr[$j]; //大于待排元素凡蚜，則后移
}else{
break;
}
}
$arr[$j+1] = $t;
}
return $arr;
}
二分插入排序
原理同上人断。 只是在第二步尋找合適位置時(shí)，使用二分查找法朝蜘，快速定位插入位置K恶迈；然后將K后的元素后移；在K位置插入待排值
復(fù)雜度：
同插入排序谱醇。
代碼實(shí)現(xiàn)：
function binary_insertion_sort($arr){
$count = count($arr);
for( $i=1; $i<$count; $i++){
$tmp = $arr[$i];
//查找需要替換的位置
$left = 0;
$right = $i-1;
while( $left <= $right){
$middle = intval( ($right+$left)/2 ); //向上加1
if( $arr[$middle] > $tmp){
$right = $middle-1;
}else{
$left = $middle+1;
}
}
//位置后的元素后移
for( $j; $j>=$left; $j--){
$arr[$j+1] = $arr[$j];
}
$arr[$left] = $tmp;
}
echo implode(',', $arr)."\r\n";
}
選擇排序
從待排序列中選擇最小(大)的元素暇仲，放在序列的起始位置；然后在從剩下的序列中繼續(xù)選擇最小(大)的元素副渴，放在已排序序列的隊(duì)尾奈附。
復(fù)雜度：
時(shí)間：O(n^2)
空間：O(1)
代碼實(shí)現(xiàn)：
略
冒泡排序
兩層循環(huán)，外層循環(huán)次數(shù)=元素個(gè)數(shù)煮剧；
內(nèi)層循環(huán)挨個(gè)比較斥滤，當(dāng) A[j] 大于 A[j+1]時(shí)交換兩個(gè)值；
當(dāng)內(nèi)循環(huán)結(jié)束時(shí)勉盅，最多有n-1次交換佑颇，會(huì)將最大值置于尾部；
當(dāng)一次外循環(huán)無元素交換時(shí)草娜，說明序列已有序挑胸，可提前結(jié)束外層循環(huán)。
復(fù)雜度
時(shí)間： o(n^2)宰闰； 最優(yōu)是已排序列進(jìn)過一層循環(huán)發(fā)現(xiàn)無元素交換茬贵，直接退出程序凸克，復(fù)雜度O(n)。
空間：O(1)
雞尾酒排序
冒泡排序的變種闷沥，不同的地方在于從低到高后從高到低。一次層循環(huán)內(nèi)完成一大一小兩個(gè)元素的冒泡咐容。
復(fù)雜度
同上
代碼實(shí)現(xiàn)
function cocktail_sort($arr){
$i=1;
$start =0;
$len = count($arr)-1;
$end = 0;
while($i>0){ //有交換元素時(shí)繼續(xù)執(zhí)行
$i=0;
for($j=$start; $j<$len-$end; $j++){
if( $arr[$j] > $arr[$j+1]){
$t = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $t;
$i=1;
}
}
//逆向冒泡來一次
for($j=$len-$end; $j>$start; $j--){
if( $arr[$j] < $arr[$j-1]){
$t = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $t;
$i=1;
}
}
$end++; //通過冒泡舆逃，尾部有序序列個(gè)數(shù)加一
$start++; //頭部有序序列個(gè)數(shù)加一
}
}
桶排序
將數(shù)組分別放到有限數(shù)量的桶中。每個(gè)桶在進(jìn)行獨(dú)立的排序戳粒。 分桶要求桶中的最大數(shù)據(jù)小于下一個(gè)桶的最小數(shù)據(jù)路狮。
復(fù)雜度
時(shí)間：
空間： O(N+M)
計(jì)數(shù)排序
1.找出待排序列的最大值和最小值；使用數(shù)組C來標(biāo)識(shí) C[min] - c[max]蔚约；
2.統(tǒng)計(jì)數(shù)組中每個(gè)值出現(xiàn)的次數(shù)奄妨，存入C[i]中；
3.反向填充目標(biāo)數(shù)組：順序遍歷這個(gè)數(shù)組C苹祟，將下標(biāo)解釋成數(shù)據(jù)砸抛， 將該位置的值表示該數(shù)據(jù)的重復(fù)數(shù)量，得到排序好的數(shù)組树枫。
注：
- 當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí)直焙，它的運(yùn)行時(shí)間是 O(n + k)。計(jì)數(shù)排序不是比較排序砂轻，排序的速度快于任何比較排序算法奔誓。
- 只能對(duì)整數(shù)進(jìn)行排序。
復(fù)雜度
時(shí)間：O(n)
空間：最大O(2n)
基數(shù)排序
將整數(shù)按位數(shù)切割成不同的數(shù)字搔涝，然后按每個(gè)位數(shù)分別比較厨喂。
位圖排序
要求數(shù)據(jù)不重復(fù)，用bit位進(jìn)行位圖排序庄呈，能節(jié)省空間蜕煌。
譬如： 每個(gè)學(xué)生答題一次，將已答題的學(xué)號(hào)記錄在文件中抒痒。學(xué)號(hào)只出現(xiàn)一次幌绍，且學(xué)號(hào)連續(xù)。輸入一個(gè)學(xué)號(hào)故响，查看是否答題傀广。
解決： 將學(xué)號(hào)進(jìn)行排序，在查找時(shí)使用二分查找彩届。 因?yàn)閷W(xué)號(hào)不重復(fù)伪冰，所以可使用位圖排序。
復(fù)雜度
位圖排序不是比較排序樟蠕，時(shí)間復(fù)雜度為 O(n)
相關(guān)閱讀:
