1. //歸并排序 
2. Array.prototype.mergeSort = function(s, e, b) { 
3.     if (s == null) 
4.         s = 0; 
5.     if (e == null) 
6.         e = this.length - 1; 
7.     if (b == null) 
8.         b = new Array(this.length); 
9.     if (s >= e) 
10.         return; 
11.     var m = (s + e) >> 1; 
12.     this.mergeSort(s, m, b); 
13.     this.mergeSort(m + 1, e, b); 
14.     for (var i = s, j = s, k = m + 1; i <= e; ++i)   
15.         b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; 
16.     for (var i = s; i <= e; ++i) 
17.         this[i] = b[i]; 
18. } 

算法性能：可以選取“歸并操作”作為基本操作，“歸并操作”即為將待歸并表中元素復(fù)制到一個存儲歸并結(jié)果的表中的過程，其次數(shù)為要歸并的兩個子序列中元素個數(shù)之和。算法總共需要進行l(wèi)ogn趟排序，每趟排序執(zhí)行n次基本操作，因此整個歸并排序中總的基本操作執(zhí)行次數(shù)為nlogn，即時間復(fù)雜度為O(nlogn)，說明歸并排序時間復(fù)雜度和初始序列無關(guān)。由于歸并排序需要轉(zhuǎn)存整個待排序列，因此空間復(fù)雜度為O(n)。

一些結(jié)論

（1）快速排序、希爾排序、歸并排序、堆排序的平均時間為O(nlogn)，其他的為O(n*n)。

（2）快速排序、希爾排序、選擇排序、堆排序不穩(wěn)定，其他的穩(wěn)定。

（3）經(jīng)過一趟排序能夠保證一個元素到達最終位置的是冒泡排序、快速排序、選擇排序、堆排序。

（4）元素比較次數(shù)和原始序列無關(guān)的是選擇排序、折半插入排序。

（5）排序趟數(shù)和原始序列有關(guān)的是交換類排序。

（6）直接插入排序和折半插入排序的區(qū)別是尋找插入位置的方式不同，一個是按順序查找方式，另一個是按折半查找方式。

 6/6   首頁 上一頁 4 5 6