常見的排序算法：

• 快速排序、堆排序、歸并排序、選擇排序
• 插入排序、二分插入排序
• 冒泡排序、雞尾酒排序
• 桶排序、計數(shù)排序、基數(shù)排序、位圖排序

一、快速排序

通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的A、B兩部分，A部分全部小于基準(zhǔn)值，B部分全部大于基準(zhǔn)值。然后在對兩部分做相同的處理，已完成排序的功能。

算法描述與分析

1. 從數(shù)列中挑選一個元素，作為基準(zhǔn)值， pivot;
2. 便利排序數(shù)列，比基準(zhǔn)值小的放在左邊A，大的放在右邊B（相同的放在任意一邊）。待分組完成后基準(zhǔn)值就處于A、B的中間位置。 這個過程稱為分區(qū)(partition)操作，兩種實(shí)現(xiàn)方式具體實(shí)現(xiàn)見代碼
3. 遞歸排序A、B兩部分，重復(fù)上面1 2兩步，進(jìn)行排序。

 

復(fù)雜度

時間復(fù)雜度:

A. o(nlogn)* : 將數(shù)組分解為一些列小問題進(jìn)行獨(dú)立解決，上述的過程重復(fù)logn次得到有序的序列； 每次都需要對n個進(jìn)行一次處理，所以時間復(fù)雜度為 n*logn

B. o(n^2）: 固定選擇第一個元素做基準(zhǔn)值，對倒序數(shù)組進(jìn)行正序排列；每次劃分只得到一個比上一次劃分少一個記錄的子序列，每次只排一個。相當(dāng)于向后冒泡排序，所以時間復(fù)雜度為o(n^2)

空間復(fù)雜度：

額外使用的空間需要看具體的代碼實(shí)現(xiàn)，理論上最優(yōu)情況下空間復(fù)雜度為o(1)，只是用一個交換空間； 如果考慮遞歸的實(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)值，取最左邊的一個元素
 $pivot = $arr[$left];
 //隨機(jī)取基準(zhǔn)值 - 避免對倒序數(shù)組進(jìn)行正序排序時，時間復(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); //對左邊內(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ū)方法. 這個思想很重要，可以在多個問題中使用。如：取前幾名、字符串大小寫字母分組等
function partition(&$arr, $left, $right){
 //隨機(jī)、取最后一個為基準(zhǔn)值，方便從頭開始遍歷
 $k = rand($left, $right);
 swap($arr, $k, $right);
 $pivot = $arr[$right]; 
 // 取兩個指針A B，從{$left}開始走，B在遇到小于基準(zhǔn)值是前走； 
 // 當(dāng)A遇到小于基準(zhǔn)值時和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)，不申請額外空間
// 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)行耗時出現(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ù)會有不同，耗時自然也就不同。

二、堆排序

利用堆這種數(shù)據(jù)結(jié)構(gòu)，堆積生成一個近似完全的二叉樹，并且滿足堆積性質(zhì)：即子節(jié)點(diǎn)的建值總是小于(或大于)它的父節(jié)點(diǎn)。 二叉樹使用數(shù)組來實(shí)現(xiàn)，從頭到尾對應(yīng)堆的從上到下。

示例

最大堆（父節(jié)點(diǎn)大于任何一個子節(jié)點(diǎn)），則根節(jié)點(diǎn)時最大值。將根節(jié)點(diǎn)取出來，剩下的進(jìn)行堆調(diào)整生成最大堆；重復(fù)上述步驟，直到堆無節(jié)點(diǎn)時完成排序。

海量數(shù)據(jù)TopK問題

用堆排序來解決海量數(shù)據(jù)TopK 問題會非常好。構(gòu)建K個節(jié)點(diǎn)的最小堆；遍歷數(shù)據(jù)，當(dāng)數(shù)據(jù)大于最小根節(jié)點(diǎn)時替換根節(jié)點(diǎn)，進(jìn)行堆調(diào)整，生成最小堆；遍歷結(jié)束時，堆會保存其中最大的K個元素； 在進(jìn)行堆排序，生成K個元素從大到小的排列。

算法描述與分析：

我們這里先介紹幾個問題，一步步推到堆排序。

什么是堆

定義上面已有說明，示例如下：

 

使用數(shù)組存儲：$arr = [1, 2, 3, 17, 19, 36, 7, 15, 170]

堆調(diào)整

為了保證堆的特性而做的一個操作。將該根節(jié)點(diǎn)就行下沉操作，一直沉到合適的位置，使得剛才的子樹滿足堆的性質(zhì)。

例如對最大堆進(jìn)行堆調(diào)整：

1.對應(yīng)的數(shù)組元素A[i], 左孩子 left(2i+1), 右孩子right(2i+2), 中找最大的那一個，將其下標(biāo)存入largest中；

2.如果A[i] 是最大的元素，則程序直接結(jié)束；

3.否則，i的某個子節(jié)點(diǎn)為最大元素，將A[i] 與 A[largest] 交換；

4.在從交換的子子節(jié)點(diǎn)開始，重復(fù)1,2,3步，直到葉子節(jié)點(diǎn)，完成一次堆調(diào)整。

建堆

建堆就是一個不斷進(jìn)行堆調(diào)整的過程。在數(shù)組中，我們一般從第n/2個數(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)行比較，

所以建堆時必須從后向前進(jìn)行，首先保證子樹滿足特性，在一步步往上推。

ps: 數(shù)組下標(biāo)從0開始，建堆節(jié)點(diǎn)應(yīng)從下標(biāo) n/2 -1 開始

堆排序

堆排序是在建堆完成之后，進(jìn)行的操作。

以最大堆為例，堆以數(shù)組形式進(jìn)行存儲，所以A[0]是最大值，將A[0]與A[n-1]交換，然后對A[0_{n-2]進(jìn)行堆調(diào)整。第二次將A[0]與A[n-2]進(jìn)行交換，A[0}n-3]進(jìn)行堆調(diào)整，重復(fù)這樣的操作直到A[0]與A[1]進(jìn)行交換。 每次都將最大的數(shù)移入后面的區(qū)間，故操作完成之后，所得的數(shù)組就是從小到大有序排列的了。

堆排序圖解

 

 

復(fù)雜度

時間復(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)."rn";
 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)."rn";
}
//建堆
function createHeap( &$arr, $heap_size){
 $n = floor($heap_size/2) -1;
 for($i=$n; $i>=0; $i-- ){ 
 // 從最后一個非葉子節(jié)點(diǎn)開始，下標(biāo)遞減進(jìn)行建堆。 
 // 保證節(jié)點(diǎn)的子樹滿足堆的性質(zhì)，才能進(jìn)一步對節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行堆調(diào)整; 否則會有問題
 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)下沉，并對下沉后的節(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)值是最大值時，結(jié)束調(diào)整。 
 // 因?yàn)椋荷顚哟蔚淖訕湓诮ǘ褧r已經(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)的個數(shù)，最大個數(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ù)字個數(shù)+1）
 $t = ceil($t);
 for($j=0; $j<$t; $j++){ echo " " ; }
 echo $arr[$i];
 if( $i+1 == $num ){
 echo "rn";
 $row++;
 $num += pow(2, $row-1);
 }
 }
 echo "rn";
}

運(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)的一個非常經(jīng)典的應(yīng)用。將大序列拆分成n個小序列，先使小序列有序，然后合并有序子序列，得到排序結(jié)果。

將兩個有序序列合并成一個序列的方法叫做2路歸并。

算法描述與分析：

遞歸方法實(shí)現(xiàn)：

1.Divide: 把長度為n的序列分成長度為 n/2的子序列；

2.Conquer: 對每個子序列采用歸并排序；

3.Combine：將排序好的兩個子序列合并成最終的排序序列。

 

歸并操作的工作原理如下：

第一步：申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列

第二步：設(shè)定兩個指針最初位置分別為兩個已經(jīng)排序序列的起始位置

第三步：比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置

重復(fù)步驟3直到某一指針超出序列尾

將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

復(fù)雜度：

時間復(fù)雜度：

O(nlogn): 將序列分成小序列需要logn步，每一步合并都需要對n個元素進(jìn)行比較，時間復(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]

四、插入排序

簡介：

構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列從后向前掃描，找到合適的位置K并插入。 位置K之后的元素需要全部后移。

算法描述與分析：

1. 取第一個元素構(gòu)建有序序列；
2. 取出下一個元素B，對有序序列從后向前掃描； 如果掃描到的元素大于B,則后移該元素；否則將B插入該元素后面；
3. 重復(fù)第2步，直到遍歷完所有數(shù)據(jù)。

 

復(fù)雜度：

時間：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;
}

五、二分插入排序

原理同上。 只是在第二步尋找合適位置時，使用二分查找法，快速定位插入位置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)."rn";
}

六、選擇排序

從待排序列中選擇最小(大)的元素，放在序列的起始位置；然后在從剩下的序列中繼續(xù)選擇最小(大)的元素，放在已排序序列的隊尾。

 

復(fù)雜度：

時間：O(n^2)

空間：O(1)

七、冒泡排序

兩層循環(huán)，外層循環(huán)次數(shù)=元素個數(shù)；

內(nèi)層循環(huán)挨個比較，當(dāng) A[j] 大于 A[j+1]時交換兩個值；

當(dāng)內(nèi)循環(huán)結(jié)束時，最多有n-1次交換，會將最大值置于尾部；

當(dāng)一次外循環(huán)無元素交換時，說明序列已有序，可提前結(jié)束外層循環(huán)。

復(fù)雜度

時間： o(n^2)； 最優(yōu)是已排序列進(jìn)過一層循環(huán)發(fā)現(xiàn)無元素交換，直接退出程序，復(fù)雜度O(n)。

空間：O(1)

八、雞尾酒排序

冒泡排序的變種，不同的地方在于從低到高后從高到低。一次層循環(huán)內(nèi)完成一大一小兩個元素的冒泡。

 

function cocktail_sort($arr){
 $i=1;
 $start =0;
 $len = count($arr)-1;
 $end = 0;
 while($i>0){ //有交換元素時繼續(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++; //通過冒泡，尾部有序序列個數(shù)加一
 $start++; //頭部有序序列個數(shù)加一
 }
}

九、桶排序

將數(shù)組分別放到有限數(shù)量的桶中。每個桶在進(jìn)行獨(dú)立的排序。 分桶要求桶中的最大數(shù)據(jù)小于下一個桶的最小數(shù)據(jù)。

復(fù)雜度

時間：

空間： O(N+M)

---

十、計數(shù)排序

1.找出待排序列的最大值和最小值；使用數(shù)組C來標(biāo)識 C[min] - c[max]；

2.統(tǒng)計數(shù)組中每個值出現(xiàn)的次數(shù)，存入C[i]中；

3.反向填充目標(biāo)數(shù)組：順序遍歷這個數(shù)組C，將下標(biāo)解釋成數(shù)據(jù)， 將該位置的值表示該數(shù)據(jù)的重復(fù)數(shù)量，得到排序好的數(shù)組。

注：

1. 當(dāng)輸入的元素是n 個0到k之間的整數(shù)時，它的運(yùn)行時間是 O(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
2. 只能對整數(shù)進(jìn)行排序。

復(fù)雜度

時間：O(n)

空間：最大O(2n)

---

十一、基數(shù)排序

將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。

---

十二、位圖排序

要求數(shù)據(jù)不重復(fù)，用bit位進(jìn)行位圖排序，能節(jié)省空間。

譬如： 每個學(xué)生答題一次，將已答題的學(xué)號記錄在文件中。學(xué)號只出現(xiàn)一次，且學(xué)號連續(xù)。輸入一個學(xué)號，查看是否答題。

解決： 將學(xué)號進(jìn)行排序，在查找時使用二分查找。 因?yàn)閷W(xué)號不重復(fù)，所以可使用位圖排序。

復(fù)雜度

位圖排序不是比較排序，時間復(fù)雜度為 O(n)