算法性能：在內(nèi)層循環(huán)中this[j]=this[j-1]，這句是作為基本操作?？紤]最壞情況，即整個序列是逆序的，則其基本操作總的執(zhí)行次數(shù)為n*(n-1)/2，其時間復(fù)雜度為O(n*n)?？紤]最好情況，即整個序列已經(jīng)有序，則循環(huán)內(nèi)的操作均為常量級，其時間復(fù)雜度為O(n)。因此本算法平均時間復(fù)雜度為O(n*n)。算法所需的額外空間只有一個value，因此空間復(fù)雜度為O(1)。

希爾排序

算法思想：希爾排序又叫做縮小增量排序，是將待排序的序列按某種規(guī)則分成幾個子序列，分別對這幾個子序列進(jìn)行插入排序，其中這一規(guī)則就是增量。如可以使用增量5、3、1來分格序列，且每一趟希爾排序的增量都是逐漸縮小的，希爾排序的每趟排序都會使得整個序列變得更加有序，等整個序列基本有序了，再使用一趟插入排序，這樣會更有效率，這就是希爾排序的思想。

1. //希爾排序 
2. Array.prototype.shellSort = function() { 
3.     for (var step = this.length >> 1; step > 0; step >>= 1) 
4.     { 
5.         for (var i = 0; i < step; ++i) 
6.         { 
7.             for (var j = i + step; j < this.length; j += step) 
8.             { 
9.                 var k = j, value = this[j]; 
10.                 while (k >= step && this[k - step] > value) 
11.                 { 
12.                     this[k] = this[k - step]; 
13.                     k -= step; 
14.                 } 
15.                 this[k] = value; 
16.             } 
17.         } 
18.     } 
19. } 

算法性能：希爾排序的時間復(fù)雜度平均情況為O(nlogn)，空間復(fù)雜度為O(1)。希爾排序的增量取法要注意，首先增量序列的最后一個值一定是1，其次增量序列中的值沒有除1之外的公因子，如8，4，2，1這樣的序列就不要?。ㄓ泄蜃?）。

 2/6   首頁 上一頁 1 2 3 4 5 6 下一頁 尾頁