本文目录一览：
最常见的算法，用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原创
转贴请注明出处
