本文目錄一覽：
最常見的算法，用PHP如何實現
1、冒泡排序
function bubble_sort($arr) {
$n=count($arr);
for($i=0;$i$n-1;$i ){
for($j=$i 1;$j$n;$j ) {
if($arr[$j]$arr[$i]) {
$temp=$arr[$i];
$arr[$i]=$arr[$j];
$arr[$j]=$temp;
}
}
}
return $arr;
}
2、歸併排序
function Merge($arr, $left, $mid, $right) {
$i = $left;
$j = $mid 1;
$k = 0;
$temp = array();
while ($i = $mid $j = $right)
{
if ($arr[$i] = $arr[$j])
$temp[$k ] = $arr[$i ];
else
$temp[$k ] = $arr[$j ];
}
while ($i = $mid)
$temp[$k ] = $arr[$i ];
while ($j = $right)
$temp[$k ] = $arr[$j ];
for ($i = $left, $j = 0; $i = $right; $i , $j )
$arr[$i] = $temp[$j];
}
function MergeSort($arr, $left, $right)
{
if ($left $right)
{
$mid = floor(($left $right) / 2);
MergeSort($arr, $left, $mid);
MergeSort($arr, $mid 1, $right);
Merge($arr, $left, $mid, $right);
}
}
3、二分查找-遞歸
function bin_search($arr,$low,$high,$value) {
if($low$high)
return false;
else {
$mid=floor(($low $high)/2);
if($value==$arr[$mid])
return $mid;
elseif($value$arr[$mid])
return bin_search($arr,$low,$mid-1,$value);
else
return bin_search($arr,$mid 1,$high,$value);
}
}
4、二分查找-非遞歸
function bin_search($arr,$low,$high,$value) {
while($low=$high) {
$mid=floor(($low $high)/2);
if($value==$arr[$mid])
return $mid;
elseif($value$arr[$mid])
$high=$mid-1;
else
$low=$mid 1;
}
return false;
}
5、快速排序
function quick_sort($arr) {
$n=count($arr);
if($n=1)
return $arr;
$key=$arr[0];
$left_arr=array();
$right_arr=array();
for($i=1;$i$n;$i ) {
if($arr[$i]=$key)
$left_arr[]=$arr[$i];
else
$right_arr[]=$arr[$i];
}
$left_arr=quick_sort($left_arr);
$right_arr=quick_sort($right_arr);
return array_merge($left_arr,array($key),$right_arr);
}
6、選擇排序
function select_sort($arr) {
$n=count($arr);
for($i=0;$i$n;$i ) {
$k=$i;
for($j=$i 1;$j$n;$j ) {
if($arr[$j]$arr[$k])
$k=$j;
}
if($k!=$i) {
$temp=$arr[$i];
$arr[$i]=$arr[$k];
$arr[$k]=$temp;
}
}
return $arr;
}
7、插入排序
function insertSort($arr) {
$n=count($arr);
for($i=1;$i$n;$i ) {
$tmp=$arr[$i];
$j=$i-1;
while($arr[$j]$tmp) {
$arr[$j 1]=$arr[$j];
$arr[$j]=$tmp;
$j–;
if($j0)
break;
}
}
return $arr;
}
php 歸併排序，，對於兩次遞歸調用自身有點不理解，求大神指教，不太明白執行過程
可以考慮把變量名修改一下
$l = $start
$m = $mid
$r = $end
這樣的話兩次調用其實也就是把整個數組先拆分成兩部分，然後這兩部分各自做排序，之後再合併
遞歸處理，如果對代碼邏輯不能直接理解的話，可以考慮從實際數據着手來理解
比如假設數組中只有一個數，程序會怎樣執行，假設數組中只有兩個數，程序會怎樣執行。。。
PHP實現常見的排序算法
註：為方便描述，下面的排序全為正序（從小到大排序）
假設有一個數組[a,b,c,d]
冒泡排序依次比較相鄰的兩個元素，如果前面的元素大於後面的元素，則兩元素交換位置；否則，位置不變。具體步驟：
1，比較a,b這兩個元素，如果ab,則交換位置，數組變為：[b,a,c,d]
2，比較a,c這兩個元素，如果ac,則位置不變，數組變為：[b,a,c,d]
3，比較c,d這兩個元素，如果cd,則交換位置，數組變為：[b,a,d,c]
完成第一輪比較後，可以發現最大的數c已經排（冒）在最後面了，接着再進行第二輪比較，但第二輪比較不必比較最後一個元素了，因為最後一個元素已經是最大的了。
第二輪比較結束後，第二大的數也會冒到倒數第二的位置。
依次類推，再進行第三輪，，，
就這樣最大的數一直往後排（冒），最後完成排序。所以我們稱這種排序算法為冒泡排序。
選擇排序是一種直觀的算法，每一輪會選出列中最小的值，把最小值排到前面。具體步驟如下:
插入排序步驟大致如下：
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來，且在大部分真實世界的數據，可以決定設計的選擇，減少所需時間的二次方項之可能性。
步驟：
從數列中挑出一個元素，稱為 「基準」（pivot），
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
歸併排序的示例代碼
歸併排序原理
歸併排序具體工作原理如下（假設序列共有n個元素）：
將序列每相鄰兩個數字進行歸併操作（merge)，形成floor(n/2)個序列，排序後每個序列包含兩個元素
將上述序列再次歸併，形成floor(n/4)個序列，每個序列包含四個元素
重複步驟2，直到所有元素排序完畢
示例代碼
Go語言 func mergeSort(r []int) []int { length := len(r) if length = 1 { return r } num := length / 2 left := mergeSort(r[:num]) right := mergeSort(r[num:]) return merge(left, right)}func merge(left, right []int) (result []int) { l, r := 0, 0 for l len(left) r len(right) { if left[l] right[r] { result = append(result, left[l]) l++ } else { result = append(result, right[r]) r++ } } result = append(result, left[l:]…) result = append(result, right[r:]…) return}Java語言 package algorithm;public class MergeSort { // private static long sum = 0; /** * pre * 二路歸併 * 原理：將兩個有序表合併和一個有序表 * /pre * * @param a * @param s * 第一個有序表的起始下標 * @param m * 第二個有序表的起始下標 * @param t * 第二個有序表的結束小標 * */ private static void merge(int[] a, int s, int m, int t) { int[] tmp = new int[t - s + 1]; int i = s, j = m, k = 0; while (i m j = t) { if (a[i] = a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; j++; k++; } } while (i m) { tmp[k] = a[i]; i++; k++; } while (j = t) { tmp[k] = a[j]; j++; k++; } System.arraycopy(tmp, 0, a, s, tmp.length); } /** * * @param a * @param s * @param len * 每次歸併的有序集合的長度 */ public static void mergeSort(int[] a, int s, int len) { int size = a.length; int mid = size / (len 1); int c = size ((len 1) - 1); // ——-歸併到只剩一個有序集合的時候結束算法——-// if (mid == 0) return; // ——進行一趟歸併排序——-// for (int i = 0; i mid; ++i) { s = i * 2 * len; merge(a, s, s + len, (len 1) + s - 1); } // ——-將剩下的數和倒數一個有序集合歸併——-// if (c != 0) merge(a, size - c - 2 * len, size - c, size - 1); // ——-遞歸執行下一趟歸併排序——// mergeSort(a, 0, 2 * len); } public static void main(String[] args) { int[] a = new int[] { 4, 3, 6, 1, 2, 5 }; mergeSort(a, 0, 1); for (int i = 0; i a.length; ++i) { System.out.print(a[i] +); } }}Python語言 def MergeSort(lists): if len(lists) = 1: return lists num = int( len(lists)/2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) return Merge(left, right)def Merge(left,right): r, l=0, 0 result=[] while llen(left) and rlen(right): if left[l] right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += right[r:] result+= left[l:] return resultprint MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])C語言 #include stdlib.h#include stdio.hvoid Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j=midIndex+1, k = startIndex; while(i!=midIndex+1 j!=endIndex+1) { if(sourceArr[i] = sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i != midIndex+1) tempArr[k++] = sourceArr[i++]; while(j != endIndex+1) tempArr[k++] = sourceArr[j++]; for(i=startIndex; i=endIndex; i++) sourceArr[i] = tempArr[i];}//內部使用遞歸void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){ int midIndex; if(startIndex endIndex) { midIndex = (startIndex + endIndex) / 2; MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex+1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); }}int main(int argc, char * argv[]){ int a[8] = {50, 10, 20, 30, 70, 40, 80, 60}; int i, b[8]; MergeSort(a, b, 0, 7); for(i=0; i8; i++) printf(%d , a[i]); printf(\n); return 0;}PHP語言 //merge函數將指定的兩個有序數組(arr1arr2,)合併並且排序//我們可以找到第三個數組,然後依次從兩個數組的開始取數據哪個數據小就先取哪個的,然後刪除掉剛剛取過///的數據functional_merge($arrA,$arrB){ $arrC = array(); while(count($arrA) count($arrB)){ //這裡不斷的判斷哪個值小,就將小的值給到arrC,但是到最後肯定要剩下幾個值, //不是剩下arrA裏面的就是剩下arrB裏面的而且這幾個有序的值,肯定比arrC裏面所有的值都大所以使用 $arrC[] = $arrA[‘0’] $arrB[‘0’] ? array_shift($arrA) : array_shift($arrB); } returnarray_merge($arrC, $arrA, $arrB);}//歸併排序主程序functional_merge_sort($arr){ $len=count($arr); if($len = 1) return $arr;//遞歸結束條件,到達這步的時候,數組就只剩下一個元素了,也就是分離了數組 $mid = intval($len/2);//取數組中間 $left_arr = array_slice($arr, 0, $mid);//拆分數組0-mid這部分給左邊left_arr $right_arr = array_slice($arr, $mid);//拆分數組mid-末尾這部分給右邊right_arr $left_arr = al_merge_sort($left_arr);//左邊拆分完後開始遞歸合併往上走 $right_arr = al_merge_sort($right_arr);//右邊拆分完畢開始遞歸往上走 $arr=al_merge($left_arr, $right_arr);//合併兩個數組,繼續遞歸 return $arr;}$arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9);print_r(al_merge_sort($arr));Pascal語言 program mergesort_1;const maxn=7;type arr=array[1..maxn] of integer;var a,b,c:arr;i:integer;procedure merge(r:arr;l,m,n:integer;varr2:arr);var i,j,k,p:integer;begin i:=l; j:=m+1; k:=l-1; while (i=m) and (j=n) do begin k:=k+1; if r[i]=r[j] then begin r2[k]:=r[i]; i:=i+1 end else begin r2[k]:=r[j]; j:=j+1; end end; if i=m then for p:=i to m do begin k:=k+1; r2[k]:=r[p]; end; if j=n then for p:=j to n do begin k:=k+1; r2[k]:=r[p]; end;end;procedure mergesort(var r,r1:arr;s,t:integer);var k:integer;c:arr;begin if s=t then r1[s]:=r[s] else begin k:=(s+t)div2; mergesort(r,c,s,k); mergesort(r,c,k+1,t); merge(c,s,k,t,r1) end;end;begin write(‘Enterdata:’); for i:=1 to maxn do read(a[i]); mergesort(a,b,1,maxn); for i:=1 to maxn do write(b[i]:9); writeln;end.//============================================program mergesort_2;const max=100000;var a,r:array[1..max] of long int;n,i:long int;procedure msort(s,t:longint);var m,i,j,k:long int;begin if s=t then exit; m:=(s+t)div2; msort(s,m); msort(m+1,t); i:=s; j:=m+1; k:=s; while (i=m) and (j=t) do begin if a[i]a[j] then begin r[k]:=a[i]; inc(i); inc(k); end else begin r[k]:=a[j]; inc(j); inc(k); end; end; while i=m do begin r[k]:=a[i]; inc(i); inc(k); end; while j=t do begin r[k]:=a[j]; inc(j); inc(k); end; for i:=s to t do a[i]:=r[i];end;begin readln(n); for i:=1 to n do read(a[i]); msort(1,n); for i:=1 to n do writeln(a[i]);end.Basic語言 Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)Dim mid As Integer = 0If firstlast Then mid = (first+last)\ 2MergeSort(Array, first, mid);MergeSort(Array, mid+1, last);Merge(Array, first, mid, last);End IfEnd Sub/*以下示例代碼實現了歸併操作。array[]是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函數將把這兩個已經排序好的子序列合併成一個排序序列。結果放到array中。*//*** 0 = p = q r, subarray array[p..q] and array[q+1..r] are already sorted.* the merge() function merges the two sub-arrays into one sorted array.*/void Merge(int array[], int p, int q, int r){ int i,k; int begin1,end1,begin2,end2; int* temp = (int*)malloc((r-p+1)*sizeof(int)); begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 = end1)( begin2 = end2)) { if(array[begin1] = array[begin2]){ temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1=end1 || begin2=end2) { if(begin1=end1) { temp[k++] = array[begin1++]; } if(begin2=end2) { temp[k++] = array[begin2++]; } } for (i = 0; i =(r – p); i++) array[p+i] = temp[i]; free(temp);}JavaScript語言
使用遞歸的代碼如下。優點是描述算法過程思路清晰，缺點是使用遞歸，mergeSort()函數頻繁地自我調用。長度為n的數組最終會調用mergeSort()函數 2n-1次，這意味着一個長度超過1500的數組會在Firefox上發生棧溢出錯誤。可以考慮使用迭代來實現同樣的功能。 function merge(left, right){ var result=[]; while(left.length0 right.length0){ if(left[0]right[0]){ /*shift()方法用於把數組的第一個元素從其中刪除，並返回第一個元素的值。*/ result.push(left.shift()); }else{ result.push(right.shift()); } } return result.concat(left).concat(right);}function mergeSort(items){ if(items.length == 1){ return items;}var middle = Math.floor(items.length/2), left = items.slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));}非遞歸算法（C++） #includeiostream#includectime#includecstring#includecstdlibusing namespace std;/**將a開頭的長為length的數組和b開頭長為right的數組合併n為數組長度，用於最後一組*/void Merge(int* data,int a,int b,int length,int n){ int right; if(b+length-1 = n-1) right = n-b; else right = length; int* temp = new int[length+right]; int i=0, j=0; while(i=length-1 j=right-1){ if(data[a+i] = data[b+j]){ temp[i+j] = data[a+i];i++; } else{ temp[i+j] = data[b+j]; j++; } } if(j == right){//a中還有元素，且全都比b中的大,a[i]還未使用 memcpy(temp + i + j, data + a + i, (length – i) * sizeof(int)); } else if(i == length){ memcpy(temp + i + j, data + b + j, (right – j)*sizeof(int)); } memcpy(data+a, temp, (right + length) * sizeof(int)); delete [] temp;}void MergeSort(int* data, int n){ int step = 1; while(step n){ for(int i=0; i=n-step-1; i+=2*step) Merge(data, i, i+step, step, n); //將i和i+step這兩個有序序列進行合併 //序列長度為step //當i以後的長度小於或者等於step時，退出 step*=2;//在按某一步長歸併序列之後，步長加倍 }}int main(){ int n; cinn; int* data = new int[n]; if(!data) exit(1); int k = n; while(k–){ cindata[n-k-1]; } clock_t s = clock(); MergeSort(data, n); clock_t e = clock(); k=n; while(k–){ coutdata[n-k-1]’ ‘; } coutendl; coutthe algorithm usede-smiliseconds.endl; delete data; return 0;}二路歸併
ConstFI=’in.txt’;FO=’out.txt’;MaxN=10000;TypeTIndex=Longint;TDat=Array[0..MaxN]OfTIndex;VarN:TIndex;Dat:TDat;Tmp:TDat;ProcedureMerge(L,Mid,R:TIndex);VarP1,P2:TIndex;E1,E2:TIndex;P:TIndex;I:TIndex;BeginP1:=L;P2:=Mid+1;P:=L;RepeatIf(Dat[P1]=Dat[P2])ThenBeginTmp[P]:=Dat[P1];Inc(P1);Inc(P);EndElseBeginTmp[P]:=Dat[P2];Inc(P2);Inc(P);End;Until(P1=Mid+1)Or(P2=R+1);If(P1=Mid+1)ThenBeginE1:=P2;E2:=R;EndElseBeginE1:=P1;E2:=Mid;End;ForI:=E1ToE2DoBeginTmp[P]:=Dat[I];Inc(P);End;End;ProcedureSort(L,R:TIndex);VarMid:TIndex=0;BeginMid:=(L+R)Shr1;If(LMid)ThenSort(L,Mid);If(Mid+1R)ThenSort(Mid+1,R);Merge(L,Mid,R);ForMid:=LToRDoDat[Mid]:=Tmp[Mid];End;ProcedureInit;VarI:TIndex;BeginFillChar(Dat,SizeOf(Dat),0);Readln(N);ForI:=1ToNDoRead(Dat[I]);End;ProcedureMain;BeginSort(1,N);End;ProcedureFinal;VarI:TIndex;BeginForI:=1ToNDoWrite(Dat[I],”);Writeln;End;BeginAssign(Input,FI);Assign(Output,FO);Reset(Input);Rewrite(Output);Init;Main;Final;Close(Input);Close(Output);End.
Delphi歸併排序完整源代碼例子： //合併子函數procedureTForm1.MergePass(vardatas:arrayofInteger;left,mid,right:Integer);vartmpArr:arrayofInteger;arrLen:Integer;i,k:Integer;begin1,begin2,end1,end2:Integer;beginarrLen:=right-left+1;SetLength(tmpArr,arrLen);begin1:=left;end1:=mid;begin2:=mid+1;end2:=right;k:=0;while((begin1=end1)and(begin2=end2))dobeginif(datas[begin1]datas[begin2])thenbegintmpArr[k]:=datas[begin1];Inc(begin1);endelsebegintmpArr[k]:=datas[begin2];Inc(begin2);end;inc(k);end;while(begin1=end1)dobegintmpArr[k]:=datas[begin1];Inc(begin1);Inc(k);end;while(begin2=end2)dobegintmpArr[k]:=datas[begin2];Inc(begin2);Inc(k);end;fori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i];end;end;//排序主函數，left是數組左下標，0開始。right是數組右下標。procedureTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);varmid:Integer;i:Integer;beginmid:=0;if(leftright)thenbeginmid:=(right+left)div2;showLog(‘中間索引：’+inttostr(mid));MergeSort(datas,left,mid);MergeSort(datas,mid+1,right);MergePass(datas,left,mid,right);showLog(‘—‘+getArrayString(datas));//顯示數組中間狀態end;end;//調用方法：procedureTForm1.btn1Click(Sender:TObject);varinArr:array[0..9]ofInteger;beginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);showLog(‘輸入數據：’+getArrayString(inArr));MergeSort(inArr,0,High(inArr));showLog(‘輸出數據：’+getArrayString(inArr));end;
歸併排序
先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合併為一個有序隊列（並輸出）？
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1
注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則複雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1
接下來的幾步如下：
A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 == B隊列：1 2 7 8 9 == B隊列：1 2 7 8 9 == B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7
我希望你明白了這是怎麼做的。這個做法顯然是正確的，複雜度顯然是線性。
歸併排序(Merge Sort)將會用到上面所說的合併操作。給出一個數列，歸併排序利用合併操作在O(nlogn)的時間內將數列從小到大排序。歸併排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合併算法把這兩段（已經排過序的）數列合併為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸併排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個算法時有人會誤以為時間複雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸併排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸併排序算法的時間複雜度為O(nlogn)。
[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]
上圖中的每一個「 \ / 」表示的是上文所述的線性時間合併操作。上圖用了4行來圖解歸併排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合併操作複雜度總和都是O(n)，那麼logn行的總複雜度為O(nlogn)。這相當於用遞歸樹的方法對歸併排序的複雜度進行了分析。假設，歸併排序的複雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間裏把分別計算出的兩組不同數據的結果合併在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這麼詭異的算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的複雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這裡的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。
歸併排序有一個有趣的副產品。利用歸併排序能夠在O(nlogn)的時間裏計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸併排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這裡我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合併的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間裏統計出A隊列的某個數比B隊列的某個數大有多少種情況。
A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 == B隊列：2 4 5 == B隊列：2 4 5 == B隊列：2 4 5 == B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4
每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合併操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。
============================華麗的分割線============================
堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這裡不重複說了。
============================華麗的分割線============================
快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間裏完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重複剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸併排序，快速排序的時間複雜度很難計算。我們可以看到，歸併排序的複雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，複雜度和前面討論的歸併排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而儘可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。
下面我們證明，快速排序算法的平均複雜度為O(nlogn)。不同的書上有不同的解釋方法，這裡我選用算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序算法的平均複雜度。證明的關鍵在於，我們需要算出某兩個元素在整個算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)=x=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設ij，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。
這裡用到了一個知識：1+1/2+1/3+…+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。
在三種O(nlogn)的排序算法中，快速排序的理論複雜度最不理想，除了它以外今天說的另外兩種算法都是以最壞情況O(nlogn)的複雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同複雜度的算法更簡潔，常數時間更小。
快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當km時，我們遞歸地尋找左邊的元素中第k小的；當km時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此複雜度大大降低。複雜度平均線性，我們不再具體證了。
還有一種算法可以在最壞O(n)的時間裏找出第k小元素。那是我見過的所有算法中最沒有實用價值的算法。那個O(n)只有理論價值。
============================華麗的分割線============================
我們前面證明過，僅僅依靠交換相鄰元素的操作，複雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序算法似乎已經是極限的時候，又是什麼制約了複雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關係，從4次比較中一共可以獲知4個大小關係。4個大小關係共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關係還需要進一步研究。第一次例外發生在n=12的時候，雖然2^2912!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序複雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這裡有一整套的理論，它叫做信息論。信息論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那信息論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。信息論和熱力學關係密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這裡不說了，有興趣可以去看《信息論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間複雜度，因為，它們排序時根本不是通過互相比較來確定大小關係的。
附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+…中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+…+1/n裏面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的複雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+…中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+…+1/n裏面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的複雜度下界。
附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!n^n，兩邊取對數我們得到log(n!)log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的複雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)….1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!(n/2)^(n/2)。兩邊取對數，log(n!)(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的複雜度下界。
今天寫到這裡了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處
原創文章，作者：簡單一點，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/127357.html
微信掃一掃 
支付寶掃一掃 
