（3）重復(fù)過(guò)程2，直到無(wú)序序列中的元素剩下1個(gè)時(shí)排序結(jié)束。

1. //堆排序 
2. Array.prototype.heapSort = function() { 
3.     for (var i = 1; i < this.length; ++i) 
4.         { 
5.         for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1) 
6.         { 
7.             if (this[k] >= this[j]) 
8.                 break; 
9.             this.swap(j, k); 
10.         } 
11.     } 
12.     for (var i = this.length - 1; i > 0; --i) 
13.     { 
14.         this.swap(0, i); 
15.         for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) 
16.         { 
17.             if (k == i || this[k] < this[k - 1]) 
18.                 --k; 
19.             if (this[k] <= this[j]) 
20.                 break; 
21.             this.swap(j, k); 
22.         } 
23.     } 
24. } 

算法性能：完全二叉樹(shù)的高度為[log(n+1)]，即對(duì)每個(gè)節(jié)點(diǎn)調(diào)整的時(shí)間復(fù)雜度為O(logn)，基本操作總次數(shù)是兩個(gè)并列循環(huán)中基本操作次數(shù)相加，則整個(gè)算法時(shí)間復(fù)雜度為O(logn)*n/2+O(logn)*(n-1)，即O(nlogn)。額外空間只有一個(gè)temp，因此空間復(fù)雜度為O(1)。

堆排序的優(yōu)點(diǎn)是適合記錄數(shù)很多的場(chǎng)景，如從1000000個(gè)記錄中選出前10個(gè)最小的，這種情況用堆排序最好，如果記錄數(shù)較少，則不提倡使用堆排序。另外，Hash表+堆排序是處理海量數(shù)據(jù)的絕佳組合，關(guān)于海量數(shù)據(jù)處理會(huì)在之后的博文中介紹到。

歸并排序

算法思想：其核心就是“兩兩歸并”，首先將原始序列看成每個(gè)只含有單獨(dú)1個(gè)元素的子序列，兩兩歸并，形成若干有序二元組，則第一趟歸并排序結(jié)束，再將這個(gè)序列看成若干個(gè)二元組子序列，繼續(xù)兩兩歸并，形成若干有序四元組，則第二趟歸并排序結(jié)束，以此類推，最后只有兩個(gè)子序列，再進(jìn)行一次歸并，即完成整個(gè)歸并排序。

 5/6   首頁(yè) 上一頁(yè) 3 4 5 6 下一頁(yè) 尾頁(yè)