Ⅰ 什麼叫歸並演算法
合並排序（MERGE SORT）是又一類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成一個新的有序數據序列，因此它又叫歸並演算法。它的基本思想就是假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。
例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那麼採用歸並排序演算法的操作過程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長度為1的7個子序列組成
第一次合並之後 [38 49] [65 97] [13 76] [27]
看成由長度為1或2的4個子序列組成
第二次合並之後 [38 49 65 97] [13 27 76]
看成由長度為4或3的2個子序列組成
第三次合並之後 [13 27 38 49 65 76 97]
合並演算法的核心操作就是將一維數組中前後相鄰的兩個兩個有序序列合並成一個有序序列。合並演算法也可以採用遞歸演算法來實現，形式上較為簡單,但實用性很差。合並演算法的合並次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這一規律,當有N個子序列時可以推斷出合並的次數是X(2 >=N,符合此條件的最小那個X)。
其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)
歸並演算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}
long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}
Ⅱ 用JS實現排序的功能
js常用排序實現，參考代碼如下
<script>
Array.prototype.swap=function(i,j)
{
vartemp=this[i];
this[i]=this[j];
this[j]=temp;
}
Array.prototype.bubbleSort=function()
{
for(vari=this.length-1;i>0;--i)
{
for(varj=0;j<i;++j)
{
if(this[j]>this[j+1])this.swap(j,j+1);
}
}
}
Array.prototype.selectionSort=function()
{
for(vari=0;i<this.length;++i)
{
varindex=i;
for(varj=i+1;j<this.length;++j)
{
if(this[j]<this[index])index=j;
}
this.swap(i,index);
}
}
Array.prototype.insertionSort=function()
{
for(vari=1;i<this.length;++i)
{
varj=i,value=this[i];
while(j>0&&this[j-1]>value)
{
this[j]=this[j-1];
--j;
}
this[j]=value;
}
}
Array.prototype.shellSort=function()
{
for(varstep=this.length>>1;step>0;step>>=1)
{
for(vari=0;i<step;++i)
{
for(varj=i+step;j<this.length;j+=step)
{
vark=j,value=this[j];
while(k>=step&&this[k-step]>value)
{
this[k]=this[k-step];
k-=step;
}
this[k]=value;
}
}
}
}
Array.prototype.quickSort=function(s,e)
{
if(s==null)s=0;
if(e==null)e=this.length-1;
if(s>=e)return;
this.swap((s+e)>>1,e);
varindex=s-1;
for(vari=s;i<=e;++i)
{
if(this[i]<=this[e])this.swap(i,++index);
}
this.quickSort(s,index-1);
this.quickSort(index+1,e);
}
Array.prototype.stackQuickSort=function()
{
varstack=[0,this.length-1];
while(stack.length>0)
{
vare=stack.pop(),s=stack.pop();
if(s>=e)continue;
this.swap((s+e)>>1,e);
varindex=s-1;
for(vari=s;i<=e;++i)
{
if(this[i]<=this[e])this.swap(i,++index);
}
stack.push(s,index-1,index+1,e);
}
}
Array.prototype.mergeSort=function(s,e,b)
{
if(s==null)s=0;
if(e==null)e=this.length-1;
if(b==null)b=newArray(this.length);
if(s>=e)return;
varm=(s+e)>>1;
this.mergeSort(s,m,b);
this.mergeSort(m+1,e,b);
for(vari=s,j=s,k=m+1;i<=e;++i)
{
b[i]=this[(k>e||j<=m&&this[j]<this[k])?j++:k++];
}
for(vari=s;i<=e;++i)this[i]=b[i];
}
Array.prototype.heapSort=function()
{
for(vari=1;i<this.length;++i)
{
for(varj=i,k=(j-1)>>1;k>=0;j=k,k=(k-1)>>1)
{
if(this[k]>=this[j])break;
this.swap(j,k);
}
}
for(vari=this.length-1;i>0;--i)
{
this.swap(0,i);
for(varj=0,k=(j+1)<<1;k<=i;j=k,k=(k+1)<<1)
{
if(k==i||this[k]<this[k-1])--k;
if(this[k]<=this[j])break;
this.swap(j,k);
}
}
}
functiongenerate()
{
varmax=parseInt(txtMax.value),count=parseInt(txtCount.value);
if(isNaN(max)||isNaN(count))
{
alert("個數和最大值必須是一個整數");
return;
}
vararray=[];
for(vari=0;i<count;++i)array.push(Math.round(Math.random()*max));
txtInput.value=array.join(" ");
txtOutput.value="";
}
functiondemo(type)
{
vararray=txtInput.value==""?[]:txtInput.value.replace().split(" ");
for(vari=0;i<array.length;++i)array[i]=parseInt(array[i]);
vart1=newDate();
eval("array."+type+"Sort()");
vart2=newDate();
lblTime.innerText=t2.valueOf()-t1.valueOf();
txtOutput.value=array.join(" ");
}
</script>
<bodyonload=generate()>
<tablestyle="width:100%;height:100%;font-size:12px;font-family:宋體">
<tr>
<tdalign=right>
<textareaid=txtInputreadonlystyle="width:100px;height:100%"></textarea>
</td>
<tdwidth=150align=center>
隨機數個數<inputid=txtCountvalue=500style="width:50px"><br><br>
最大隨機數<inputid=txtMaxvalue=1000style="width:50px"><br><br>
<buttononclick=generate()>重新生成</button><br><br><br><br>
耗時(毫秒)：<labelid=lblTime></label><br><br><br><br>
<buttononclick=demo("bubble")>冒泡排序</button><br><br>
<buttononclick=demo("selection")>選擇排序</button><br><br>
<buttononclick=demo("insertion")>插入排序</button><br><br>
<buttononclick=demo("shell")>謝爾排序</button><br><br>
<buttononclick=demo("quick")>快速排序(遞歸)</button><br><br>
<buttononclick=demo("stackQuick")>快速排序(堆棧)</button><br><br>
<buttononclick=demo("merge")>歸並排序</button><br><br>
<buttononclick=demo("heap")>堆排序</button><br><br>
</td>
<tdalign=left>
<textareaid=txtOutputreadonlystyle="width:100px;height:100%"></textarea>
</td>
</tr>
</table>
</body>
Ⅲ JS中的各種排序方法
數據結構演算法中排序有很多種，常見的、不常見的，至少包含十種以上。根據它們的特性，可以大致分為兩種類型：比較類排序和非比較類排序
冒泡排序是一次比較兩個元素，如果順序是錯誤的就把它們交換過來。，直到不需要再交換
快速排序的基本思想是通過一趟排序，將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可以分別對這兩部分記錄繼續進行排序，以達到整個序列有序
從數列中挑出一個元素，稱為 「基準」（pivot）；然後重新排序數列，所有元素比基準值小的擺放在基準前面、比基準值大的擺在基準的後面；在這個區分搞定之後，該基準就處於數列的中間位置；然後把小於基準值元素的子數列（left）和大於基準值元素的子數列（right）遞歸地調用 quick 方法排序完成，這就是快排的思路
通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入，從而達到排序的效果
插入排序的思路是基於數組本身進行調整的，首先循環遍歷從 i 等於 1 開始，拿到當前的 current 的值，去和前面的值比較，如果前面的大於當前的值，就把前面的值和當前的那個值進行交換，通過這樣不斷循環達到了排序的目的
將最小的元素存放在序列的起始位置，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序的序列後面……以此類推，直到所有元素均排序完畢
堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質，即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆的底層實際上就是一棵完全二叉樹，可以用數組實現
歸並排序是建立在歸並操作上的一種有效的排序演算法，該演算法是採用分治法的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並
通過 mid 可以把該數組分成左右兩個數組，分別對這兩個進行遞歸調用排序方法，最後將兩個數組按照順序歸並起來
Ⅳ 歸並排序
先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？
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)，假設i<j，那麼第一次出現在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小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第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^29>12!，但現已證明給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原創
轉貼請註明出處
Ⅳ JS數組排序
JS數組排序方法有兩個： reverse() 和 sort() ，其中 reverse() 可將數組進行倒序，而 sort() 則可將數組項靈活地進行升序或降序排列。
可以看出， reverse() 會直接改變原數組，並且返回值也是倒序後的數組。
記得當年學C語言時，要學各種各樣的排序演算法，比如經典的冒泡排序法、二分排序法等，現在拋開這些演算法不說，JS就自帶原生的排序函數，用起來非常方便，它就是 sort() 。
可以看出， sort() 不傳參數時會按升序方式對數組項進行排序，並且與 reverse() 一樣既改變原數組，同時返回的也是排序後的數組。
我們再來看下一個例子：
這時你可能會說，不對呀，最終排序返回的不應該是 [8, 9, 16, 90] 嗎？然鵝事實返回的卻是 [16, 8, 9, 90] ，這到底是哪門子邏輯？
事實上， sort() 並不是按照數值進行排序，而是按字元串字母的ASCII碼值進行比較排序的，所以當數組項為數字時， sort() 也會自動先將數字轉換成字元串，然後再按字母比較的規則進行排序處理。
現在我們再回頭看看前面兩個例子。當 arr 為 [8,4,9,1] 時，數組每一項轉換成字元串後進行排序的結果正好與數字排序結果相同；而當 arr 為 [8,90,9,16] 時，數組每一項轉換成字元串後就得按順序一位一位進行比較，比如升序排序時，「16」應該排在最前面，因為「16」的第一位是「1」，比「8」和「9」的ASCII碼值都要小。
啰嗦了這么多，其實我們實際很少會使用這種排序方式，而更多的應該就是純數字的排序。那麼我們該如何正確地使用 sort() 來達到預期的排序效果呢？
接下來就來看看傳參後的 sort() 能給我們怎樣的精彩表現。
這個函數參數功能其實很簡單，實際上就是告訴 sort() 排序方式到底是升序還是降序，我們還是來看具體實例吧~
這種用法的規則是，當 sort() 傳入函數中的第一個參數a位於第二個參數b之前，則返回一個負數，相等則返回0，a位於b之後則返回正數。
比如，當要做升序排序時，我們需要想到前面的數肯定是要比後面的數小，所以傳入的這個函數參數返回值應該要是個負數，因此函數參數返回 a - b 。
如果實在不好理解，我們可以乾脆記下來， a - b 升序， b - a 降序，但是需要注意的是，如果按照這種記憶方式的話，函數括弧內的兩個參數 a 和 b 的書寫順序可不能顛倒哦~
Ⅵ 用Javascript寫排序演算法的動畫演示
1.讓JavaScript暫停下來，慢下來。
JavaScript排序是很快的，要我們肉眼能看到它的實現過程，我首先想到的是讓排序慢下來。 排序的每一個循環都讓它停300ms然後再繼續進行。 怎麼樣才能停下來呢。查了一下JavaScript貌似沒有sleep()這樣的函數。暫停做不到，但是可以想辦法讓實現跟暫停差不多的效果。比如在循環里做一些無關的事情 。
首先嘗試了讓while(true)來一直執行一個空操作。執行一段時間再回到排序邏輯。代碼大致是這樣：
for (var i = 0; i < 3; i++) {
document.writeln(i); //DOM操作
var now = new Date().getTime();
while(new Date().getTime() - now < 3000){}
}
慢是慢下來了。不過太耗資源，排序進行過程中dom並不會有任何改變，直到排序結束， DOM會變成排序好之後的樣子。 但是如果設置斷點一步步執行的時候 又可以看到一步步的排序變化。估計是因為這個操作太耗資源導致瀏覽器下達了一個DOM操作的命令但是一直騰不出資源來進行DOM操作。所以真正DOM操作的時候在js代碼執行結束之後。
所以讓JavaScript排序慢來來還是沒有實現。
另一種讓JavaScript暫停下來的思路：
寫這個文章的時候又想到一種方法來讓JavaScript停下來。 那就是AJAX的同步請求，以及超時操作。 也就是在要停下來的地方放一個AJAX請求，同步請求， 然後設置超時。超時的時間就是我們要暫停的時間。為了避免在到達超時請求之前服務 器就返回了我們的AJAX請求。可以在服務端運行類似 sleep()的程序 。從而保證AJAX不會返回。直接超時然後返回到我們的循環。不過這只是個設想。有興趣的可以去嘗試一下。
2.閉包和定時器。 這種思路不需要讓排序過程慢下來。而是使用閉包緩存排序過程中數組的變化。然後使用setTimeout來確定展示每一個數組狀態的順序。在排序循環中放入類似下面的代碼。
(function(){
var theArr = arr.slice();//當前數組狀態的備份
setTimeout(function(){
bubbleSortDom(theArr);//排序的DOM操作。
},500*timeCount);
timeCount++;//定時器的順序。
})();
不過後來發現這樣子寫的話代碼量會比較大，邏輯有修改的話要修改的地方會有點多。局限性很多，比如要實現排序動畫加快或減慢操作幾乎是很困難的。所以還要另想辦法。
3.緩存排序中的數組狀態。
也就是在排序過程中。將數組的每一輪循環的狀態保存到一個數組。然後再用這個數組依次將排序狀態保存下來。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);
這樣就只需要一個setInterval()就可以了。並且可以很方便的實現動畫的加快與減慢。邏輯也比較好理解 。
問題二：如何實現JavaScript排序動畫的加快與減慢。
我們問題一使用的第三種方法。 得到一個保存了每一步排序狀態的數組arr。 然後我們可以使用一個setInterval()定時器一步步展現排序狀態。 如果要加快速度或減慢速度。就clearInterval()，修改定時器的執行間隔，重新setInterval()，從前一個定時器執行到數組中的位置開始執行。
問題三：對於使用遞歸實現的數組怎麼辦？ 不是在原數組上進行操作的怎麼辦？
使用遞歸實現的排序。 可能並沒有在一個數組上進行操作，只是最後返回一個排序好的數組出來。那麼我們要如何獲得排序中的數組的完整狀態呢。
比如快速排序。
最開始不考慮動畫，我的實現是這樣的：
function quickSort(arr){
var len = arr.length,leftArr=[],rightArr=[],tag;
if(len<2){
return arr;
}
tag = arr[0];
for(i=1;i<len;i++){
if(arr[i]<=tag){
leftArr.push(arr[i])
}else{
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag,quickSort(rightArr));
}
然後為了考慮動畫，我改寫了它的邏輯，讓它在同一個數組上進行了實現。 其實是在遞歸的時候傳入了當前的的子數組在原數組中的起始位置。從而在原數組上進行了操作。
用了兩種方法來實現方式。在排序邏輯上略有不同。
第一種是先跟遠處的對比。遇到比自己小的放到自己前面去。循環序號+1。比自己大的放到當前排序子數組的最後面去，循環序號不變。直到排列完成。
這種方法的缺點是即使是一個有序數組。它也會重新排。
第二種方法是 除了標記位，再設置一個對比位。 遇到比自己小的，放到前面去，標記位的位置+1，標記位與對比位之間所有的往後面移動一個位置。
遇到比自己大的。標記位不變，對比位+1。
這種方法的缺點是對數組進行的操作太多。優點是對有序數組不會再排。
方式一：
function quickSort(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if((len == 2 && arr[0] == arr[1])||len<2){
return arr;
}
tag = qArr[a];
for (i = 1; i < len;) {
if(qArr[a+i]<=tag){
leftArr.push(qArr[a+i]);
qArr[a+i-1] = qArr[a+i];
qArr[a+i] = tag;
k = a+i;
i++;
}else{
if(leftArr.length+rightArr.length == len-1){
break;
}
temp = qArr[a+i];
qArr[a+i] = qArr[b-rightArr.length];
qArr[b-rightArr.length] = temp;
rightArr.push(temp);
k = a+i-1;
}
this.pushHis(qArr.slice(),a,b,k);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr
}
方式二：
function quickSort2(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if(len<2){
return arr;
}
if(len == 2 && arr[0] == arr[1]){
return arr;
}
tag = qArr[a];
for (i = 1,k = 0; i < len;) {
if(qArr[a+i]>=tag){
rightArr.push(qArr[a+i]);
i++;
}else{
temp = qArr[a+i];
for(j = a+i;j>a+k;j--){
qArr[j] = qArr[j-1];
// this.pushHis(qArr.slice(),a,b,a+k);
}
qArr[a+k] = temp;
leftArr.push(temp);
k++;
i++;
}
this.pushHis(qArr.slice(),a,b,a+k,i-1);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr;
}
具體的不同下面會有動畫演示。
問題四：動畫的流暢。
排序動畫的DOM操作是很多的很快的。這里我做的優化只是讓每一個排序步驟只涉及一個DOM操作。 全部由JavaScript拼接好，一次替換。類似下面的代碼。
效果圖：
主要實現了：
冒泡排序JavaScript動畫演示
插入排序JavaScript動畫演示
選擇排序JavaScript動畫演示
快速排序JavaScript動畫演示
歸並排序JavaScript動畫演示
希爾排序JavaScript動畫演示
Ⅶ 前端常用的一些演算法
/*去重*/
function delRepeat(arr){
var newArray=new Array();
var len=arr.length;
for(var i=0;i
for(var j=i+1;j
{
if(arr[i]==arr[j])
{
++i;
}
}
newArray.push(arr[i]);
}
return newArray;
}
var arr=new Array("red","red","1","5","2");
alert(delRepeat(arr));
/*二分法*/
又稱為折半查找演算法，但是有缺陷就是要求數字是預先排序好的
function binary(items,value){
var startIndex=0,
stopIndex=items.length-1,
midlleIndex=(startIndex+stopIndex)>>>1;
while(items[middleIndex]!=value && startIndex
if(items[middleIndex]>value){
stopIndex=middleIndex-1;
}else{
startIndex=middleIndex+1;
}
middleIndex=(startIndex+stopIndex)>>>1;
}
return items[middleIndex]!=value ? false:true;
}
/*十六進制顏色值的隨機生成*/
function randomColor(){
var arrHex=["0","2","3","4","5","6","7","8","9","a","b","c","d"],
strHex="#",
index;
for(var i=0;i<6;i++){
index=Math.round(Math.random()*15);
strHex+=arrHex[index];
}
return strHex;
}
/*一個求字元串長度的方法*/
function GetBytes(str){
var len=str.length,
bytes=len;
for(var i=0;i
if(str.CharCodeAt>255){
bytes++;
}
}
return bytes;
}
/*插入排序*/
所謂的插入排序，就是將序列中的第一個元素看成一個有序的子序列，然後不段向後比較交換比較交換。
function insertSort(arr){
var key;
for(var j = 1; j < arr.length ; j++){
//排好序的
var i = j - 1;
key = arr[j];
while(i >= 0 && arr[i] > key){
arr[i + 1] = arr[i];
i --;
}
arr[i + 1] = key;
}
return arr;
}
/*希爾排序*/
希爾排序 ，也稱 遞減增量排序演算法
其實說到底也是插入排序的變種
function shellSort(array){
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse()在維基上看到這個最優的步長較小數組
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < stepArrLength; i++){
if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
//排序一個步長
function stepSort(step){
//console.log(step)使用的步長統計
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;
for(;i < step; i++){//依次循環列
for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循環每列的每行
tem = f = step * j + i;
key = array[f];
while((tem-=step) >= 0){//依次向上查找
if(array[tem] > key){
array[tem+step] = array[tem];
}else{
break;
}
}
array[tem + step ] = key;
}
}
}
return array;
}
/*快速排序*/
快速排序演算法就系對冒泡排序的一種改進，採用的就是演算法理論中的分治遞歸的思想。
具體做法：通過一趟排序將待排序的紀錄分割成兩部分，其中一部分的紀錄值比另外一部分的紀錄值要小，就可以繼續分別對這兩部分紀錄進行排序；不段的遞歸實施上面兩個操作，從而實現紀錄值的排序。
function sort(arr){
return quickSort(arr,0,arr.length-1);
function quickSort(arr,l,r){
if(l
var mid=arr[parseInt((l+r)/2)],i=l-1,j=r+1;
while(true){
//大的放到右邊，小的放到左邊, i與j均為游標
while(arr[++i]
while(arr[--j]>mid);
if(i>=j)break;//判斷條件
var temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
quickSort(arr,l,i-1);
quickSort(arr,j+1,r);
}
return arr;
}
}
function main(){
var list=new Array(49,38,65,97,76,13,27);
document.write(sort(list).valueOf());
}
main();
/*冒泡法*/
function bullSort(array){
var temp;
for(var i=0;i
for(var j=array.length-1;j>i;j--){
if(array[j]
temp = array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
return array;
}
/*js遞歸實現方案*/
遞歸函數是在一個函數通過調用自身的情況下去解決的：
方式如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*factorial(num-1);
}
}
但是這在js裡面可能會出現錯誤：
var anotherFactorial = factorial;
factorial=null;
alert(anoterFactorial(4));
因為在調用anoterFactorial時內部的factorial已經不存在了。
解決方法是通過arguments.callee來解決。
如下：
function factorial(num){
if(num<=1){
return 1;
}else{
return num*arguments.callee(num-1);
}
var anotherFactorial = factorial;
factorial = null;
alert(anotherFactorial(4));
成功！！！！
}
/**js模擬多線程**/
if (Array.prototype.shift==null)
Array.prototype.shift = function (){
var rs = this[0];
for (var i=1;i
this.length=this.length-1
return rs;
}
if (Array.prototype.push==null)
Array.prototype.push = function (){
for (var i=0;i
return this.length;
}
var commandList = [];
var nAction = 0;//控制每次運行多少個動作
var functionConstructor = function(){}.constructor;
function executeCommands(){
for (var i=0;i
if (commandList.length>0){
var command = commandList.shift();
if (command.constructor == functionConstructor)
if (command.scheleTime == null || new Date()-command.scheleTime>0)
command();
else
commandList.push(command);
}
}
function startNewTask(){
var resultTemp = document.getElementById("sampleResult").cloneNode(true);
with (resultTemp){
id="";style.display="block";style.color=(Math.floor(Math.random()* (1<<23)).toString(16)+"00000").substring(0,6);
}
document.body.insertBefore(resultTemp,document.body.lastChild);
commandList.push(function(){simThread(resultTemp,1);});
nAction++;
}
function simThread(temp,n){
if (temp.stop) n--;
else temp.innerHTML = temp.innerHTML - (-n);
if (n<1000)
commandList.push(function(){simThread(temp,++n)});
else{
var command = function(){document.body.removeChild(temp);;nAction--;};
command.scheleTime = new Date()-(-2000);
commandList.push(command);
}
}
window.onload = function(){setInterval("executeCommands()",1);}
/
/*選擇法排序*/
選擇法主要有三種：
《1》簡單的選擇排序：簡單的前後交互。
/*簡單選擇法排序*/
其實基本的思想就是從待排序的數組中選擇最小或者最大的，放在起始位置，然後從剩下的數組中選擇最小或者最大的排在這公司數的後面。
function selectionSort(data)
{
var i, j, min, temp , count=data.length;
for(i = 0; i < count - 1; i++) {
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{ if (data[j] < data[min])
{ min = j;}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
return data;
}
《2》樹型排序：又稱錦標賽排序，首先對n個元素進行兩兩比較，然後在其中[n/2]個較小者再進行兩兩比較如此重復直至選出最小的關鍵字的紀錄為止。（可用完全二差樹表示）。缺點：輔助空間需求過大，和「最大值」進行多餘比較
《3》堆排序：（不適用於紀錄數較少的文件）
堆排序演算法的過程如下:
1)得到當前序列的最小(大)的元素
2)把這個元素和最後一個元素進行交換,這樣當前的最小(大)的元素就放在了序列的最後,而原先的最後一個元素放到了序列的最前面
3)的交換可能會破壞堆序列的性質(注意此時的序列是除去已經放在最後面的元素),因此需要對序列進行調整,使之滿足於上面堆的性質.
重復上面的過程,直到序列調整完畢為止.
js實現：
/**
*堆排序
* @param items數組
* @return排序後的數組
*/
function heapSort(items)
{
items = array2heap(items); //將數組轉化為堆
for(var i = items.length - 1; i >= 0; i--)
{
items = swap(items, 0, i); //將根和位置i的數據交換(用於將最大值放在最後面)
items = moveDown(items, 0, i - 1); //數據交換後恢復堆的屬性
}
return items;
}
/**
*將數組轉換為堆
* @param items數組
* @return堆
*/
function array2heap(items)
{
for(var i = Math.ceil(items.length / 2) - 1; i >= 0; i--)
{
items = moveDown(items, i, items.length - 1); //轉換為堆屬性
}
return items;
}
/**
*轉換為堆
* @param items數組
* @param first第一個元素
* @param last最後一個元素
* @return堆
*/
function moveDown(items, first, last)
{
var largest = 2 * first + 1;
while(largest <= last)
{
if(largest < last && items[largest] < items[largest + 1])
{
largest++;
}
if(items[first] < items[largest])
{
items = swap(items, first, largest); //交換數據
first = largest; //往下移
largest = 2 * first + 1;
}
else
{
largest = last + 1; //跳出循環
}
}
return items;
}
/**
*交換數據
* @param items數組
* @param index1索引1
* @param index2索引2
* @return數據交換後的數組
*/
function swap(items, index1, index2)
{
var tmp = items[index1];
items[index1] = items[index2];
items[index2] = tmp;
return items;
}
var a = [345,44,6,454,10,154,3,12,11,4,78,9,0,47,88,9453,4,65,1,5];
document.write(heapSort(a));
所謂歸並就是將兩個或者兩個以上的有序表合成一個新的有序表。
遞歸形式的演算法在形式上較為簡潔但實用性較差，與快速排序和堆排序相比，歸並排序的最大特點是，它是一種穩定的排序方法。
js實現歸並：
function MemeryArray(Arr,n, Brr, m)
{ var i, j, k;
var Crr=new Array();
i = j = k = 0;
while (i < n && j < m)
{
if (Arr[i] < Brr[j])
Crr[k++] = Arr[i++];
else
Crr[k++] = Brr[j++];
}
while (i < n)
Crr[k++] = Arr[i++];
while (j < m)
Crr[k++] = Brr[j++];
return Crr;
}
var Arr=new Array(45,36,89,75,65);
var Brr=new Array(48,76,59,49,25);
alert(MemeryArray(Arr , Arr.length , Brr , Brr.length));
歸並排序待續，先睡了：
歸並排序：
//將有二個有序數列a[first...mid]和a[mid...last]合並。
function mergearray(Arr,first,mid,last,tempArr)
{
var i = first, j = mid + 1;
var m = mid, n = last;
var k = 0;
while (i <= m && j <= n)
{
if (Arr[i] < Arr[j])
tempArr[k++] = Arr[i++];
else
tempArr[k++] = Arr[j++];
}
while (i <= m)
tempArr[k++] = Arr[i++];
while (j <= n)
tempArr[k++] = Arr[j++];
for (i = 0; i < k; i++)
Arr[first + i] = tempArr[i];
}
function mergesort(Arr,first,last)
{
var tempArr=new Array();
if (first < last)
{
var mid = (first + last)>>>1;
mergesort(Arr, first, mid, tempArr); //左邊有序
mergesort(Arr, mid + 1, last, tempArr); //右邊有序
mergearray(Arr, first, mid, last, tempArr); //再將二個有序數列合並
}
return Arr;
}
var Arr=new Array(1,65,45,98,56,78);
alert(mergesort(Arr,0,Arr.length-1));
/*比較兩個字元串的相似性－Levenshtein演算法簡介*/
問題與描述：
近似字元串匹配問題
說明：設給定樣本，對於任意文本串，樣本P在文本T中的K-近似匹配（K-approximate match）是指P在T中包含最多K個差異的匹配，這里的差別指：
（1）修改：P與T中對應的字元不同
（2）刪除：T中含有一個未出現在P中的字元
（3）插入：T中不包含出現在P中的一個字元
（也就是編輯距離問題）
例如：
T: a p r o x i o m a l l y
P: a p p r o x i m a t l y
經過1：插入2：刪除3：修改
那麼就是一個3-近似問題
事實上，兩個字元串可能有不得出不同的差別數量，所以K-近似匹配要求：
（1）差別數最多為K個
（2）差別數為所有匹配方式下最少的稱為編輯距離
（字元串T到P最少的差別數稱為T和P的編輯距離）
試驗要求：
（1）利用動態規劃方法給出兩個字元串編輯距離的演算法
（2）分析復雜度
（3）考慮其它方法
Levenshtein Distance來文史特距離
goodzzp
LD也叫edit distance，它用來表示2個字元串的相似度，不同於Hamming Distance，它可以用來比較2個長度不同的字元串。LD定義為需要最少多少步基本操作才能讓2個字元串相等，基本操作包含3個：
1，插入；
2，刪除；
3，替換；
比如，kiteen和sitting之間的距離可以這么計算：
1，kitten – > sitten,替換k為s；
2，sitten – > sittin,替換e為i;
3，sittin – > sitting,增加g；
所以，其LD為3；
計算LD的演算法表示為：
int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1,// deletion
d[i , j-1] + 1,// insertion
d[i-1, j-1] + cost// substitution
)
return d[lenStr1, lenStr2]；
這個演算法其實就是一個矩陣的計算：
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
首先給定第一行和第一列，然後，每個值d[i,j]這樣計算：d[i,j] = min(d[i-1,j]+ 1,d[i,j-1] +1,d[i-1,j-1]+(str1[i] == str2[j]?0:1));
最後一行，最後一列的那個值就是LD的結果。
LD(str1,str2) <= max(str1.len,str2.len)；
有人提出了Levenshtein automaton（Levenshtein自動機）來計算和某個字元串距離小於某個值的集合。這樣能夠加快近似字元串的計算過程。見文獻：Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.
A Guided Tour to Approximate String Matching GONZALONAVARRO
這篇文章裡面對這個方面（字元串相似）進行了很多描述。其中，包含了動態規劃法計算Edit distance的方法。
js實現：
//求兩個字元串的相似度,返回差別字元數,Levenshtein Distance演算法實現
function Levenshtein_Distance(s,t){
var n=s.length;// length of s
var m=t.length;// length of t
var d=[];// matrix
var i;// iterates through s
var j;// iterates through t
var s_i;// ith character of s
var t_j;// jth character of t
var cost;// cost
// Step 1
if (n == 0) return m;
if (m == 0) return n;
// Step 2
for (i = 0; i <= n; i++) {
d[i]=[];
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}else{
cost = 1;
}
// Step 6
d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7
return d[n][m];
}
//求兩個字元串的相似度,返回相似度百分比
function Levenshtein_Distance_Percent(s,t){
var l=s.length>t.length?s.length:t.length;
var d=Levenshtein_Distance(s,t);
return (1-d/l).toFixed(4);
}
//求三個數字中的最小值
function Minimum(a,b,c){
return a
}
var str1="ddsddf",str2="xdsfsx";
alert(Levenshtein_Distance_Percent(str1,str2));
Ⅷ 如何對兩個數組歸並排列排序
把數據存到一個新的數組里即可。
歸並排序演算法就是利用分治思想將數組分成兩個小組A，B，再將A，B小組各自分成兩個小組，依次類推，直到分出來的小組只有一個數據時，可以認為這個小組已經是有序的了，然後再合並相鄰的二個小組就可以。
Ⅸ JS常見排序演算法
排序演算法說明:
（1）對於評述演算法優劣術語的說明
穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
內排序 ：所有排序操作都在內存中完成；
外排序 ：由於數據太大，因此把數據放在磁碟中，而排序通過磁碟和內存的數據傳輸才能進行；
時間復雜度 : 一個演算法執行所耗費的時間。
空間復雜度 : 運行完一個程序所需內存的大小。
(2)排序演算法圖片總結:
1.冒泡排序:
解析：1.比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。
2.第一輪的時候最後一個元素應該是最大的一個。
3.按照步驟一的方法進行相鄰兩個元素的比較，這個時候由於最後一個元素已經是最大的了，所以最後一個元素不用比較。
2.快速排序:
解析：快速排序是對冒泡排序的一種改進，第一趟排序時將數據分成兩部分，一部分比另一部分的所有數據都要小。然後遞歸調用，在兩邊都實行快速排序。
3.插入排序:
解析：
（1） 從第一個元素開始，該元素可以認為已經被排序
（2） 取出下一個元素，在已經排序的元素序列中從後向前掃描
（3） 如果該元素（已排序）大於新元素，將該元素移到下一位置
（4） 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
（5）將新元素插入到下一位置中
（6） 重復步驟2
2.二分查找:
解析：二分查找，也為折半查找。首先要找到一個中間值，通過與中間值比較，大的放又，小的放在左邊。再在兩邊中尋找中間值，持續以上操作，直到找到所在位置為止。
（1）遞歸方法
（2）非遞歸方法
4.選擇排序:
解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢。
5.希爾排序:
解析:先將整個待排序的記錄序列分割成為若乾子序列分別進行直接插入排序
6.歸並排序:
解析:歸並排序是一種穩定的排序方法。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
7.堆排序:
解析:堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是
小於（或者大於）它的父節點。
8.計數排序:
解析:計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。
9.桶排序:
解析:假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排
10.基數排序:
解析:基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優
先級排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以是穩定的。
基數排序 vs 計數排序 vs 桶排序
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶 計數排序：每個桶只存儲單一鍵值 桶排序：每個桶存儲一定范圍的數值
Ⅹ 歸並排序的演算法原理是什麼
歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，歸並排序將兩個已排序的表合並成一個表。
歸並排序基本原理
通過對若干個有序結點序列的歸並來實現排序。
所謂歸並是指將若干個已排好序的部分合並成一個有序的部分。
歸並排序基本思想
設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合並到一個局部的暫存序列 temp (相當於輸出序列)中，待合並完成後將 temp 復制回 array[low..high]中，從而完成排序。
在具體的合並過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然後將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩餘記錄依次復制到 array 中即可。