各大排序算法性能比较及演示实例

算法性能：在内层循环中this[j]=this[j-1]，这句是作为基本操作。考虑最坏情况，即整个序列是逆序的，则其基本操作总的执行次数为n*(n-1)/2，其时间复杂度为O(n*n)。考虑最好情况，即整个序列已经有序，则循环内的操作均为常量级，其时间复杂度为O(n)。因此本算法平均时间复杂度为O(n*n)。算法所需的额外空间只有一个value，因此空间复杂度为O(1)。

希尔排序

算法思想：希尔排序又叫做缩小增量排序，是将待排序的序列按某种规则分成几个子序列，分别对这几个子序列进行插入排序，其中这一规则就是增量。如可以使用增量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. } 

算法性能：希尔排序的时间复杂度平均情况为O(nlogn)，空间复杂度为O(1)。希尔排序的增量取法要注意，首先增量序列的最后一个值一定是1，其次增量序列中的值没有除1之外的公因子，如8，4，2，1这样的序列就不要取（有公因子2）。

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