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

（3）重复过程2，直到无序序列中的元素剩下1个时排序结束。

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. } 

算法性能：完全二叉树的高度为[log(n+1)]，即对每个节点调整的时间复杂度为O(logn)，基本操作总次数是两个并列循环中基本操作次数相加，则整个算法时间复杂度为O(logn)*n/2+O(logn)*(n-1)，即O(nlogn)。额外空间只有一个temp，因此空间复杂度为O(1)。

堆排序的优点是适合记录数很多的场景，如从1000000个记录中选出前10个最小的，这种情况用堆排序最好，如果记录数较少，则不提倡使用堆排序。另外，Hash表+堆排序是处理海量数据的绝佳组合，关于海量数据处理会在之后的博文中介绍到。

归并排序

算法思想：其核心就是“两两归并”，首先将原始序列看成每个只含有单独1个元素的子序列，两两归并，形成若干有序二元组，则第一趟归并排序结束，再将这个序列看成若干个二元组子序列，继续两两归并，形成若干有序四元组，则第二趟归并排序结束，以此类推，最后只有两个子序列，再进行一次归并，即完成整个归并排序。

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