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

冒泡排序

算法思想：通过一系列的“交换”动作完成的，首先第一个记录与第二个记录比较，如果第一个大，则二者交换，否则不交换；然后第二个记录和第三个记录比较，如果第二个大，则二者交换，否则不交换，以此类推，最终最大的那个记录被交换到了最后，一趟冒泡排序完成。在这个过程中，大的记录就像一块石头一样沉底，小的记录逐渐向上浮动。冒泡排序算法结束的条件是一趟排序没有发生元素交换。

1. //冒泡排序 
2. Array.prototype.bubbleSort = function() { 
3.     for (var i = this.length - 1; i > 0; --i) 
4.     { 
5.         for (var j = 0; j < i; ++j) 
6.             if (this[j] > this[j + 1]) 
7.                 this.swap(j, j + 1); 
8.     } 
9. } 

算法性能：最内层循环的元素交换操作是算法的基本操作。最坏情况，待排序列逆序，则基本操作的总执行次数为(n-1+1)*(n-1)/2=n(n-1)/2，其时间复杂度为O(n*n)；最好情况，待排序列有序，则时间复杂度为O(n)，因此平均情况下的时间复杂度为O(n*n)。算法的额外辅助空间只有一个用于交换的temp，所以空间复杂度为O(1)。

快速排序

算法思想：以军训排队为例，教官说以第一个同学为中心，比他矮的站他左边，比他高的站他右边，这就是一趟快速排序。因此，一趟快速排序是以一个枢轴，将序列分成两部分，枢轴的一边比它小（或小于等于），另一边比它大（或大于等于）。

1. //递归快速排序 
2. Array.prototype.quickSort = function(s, e) { 
3.     if (s == null) 
4.         s = 0; 
5.     if (e == null) 
6.         e = this.length - 1; 
7.     if (s >= e) 
8.         return; 
9.     this.swap((s + e) >> 1, e); 
10.     var index = s - 1; 
11.     for (var i = s; i <= e; ++i)   
12.         if (this[i] <= this[e]) this.swap(i, ++index); 
13.     this.quickSort(s, index - 1); 
14.     this.quickSort(index + 

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