归并排序算法的基本特性：
最差时间复杂度：O(N * logN)
最优时间复杂度：O(N)
平均时间复杂度：O(N * logN)
最差空间复杂度：O(N)
归并操作的过程如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
测试结果：
数组里有10000个随机数, 执行100次后花费的毫秒数
最大毫秒数为67
最小毫秒数为47
平均毫秒数为49
示例代码：
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>归并排序算法</title>
</head>
<body>
<script>
var count = 10000,
num = testCount = 100,
i,
exeCount,
exeTimeArr = [],
mergeSort = function(a){
var merge = function(arr1, arr2){
var result = [];
while(true) {
if(arr1.length == 0 || arr2.length == 0){
return result.concat( arr1.concat( arr2 ) );
}
arr1[0] < arr2[0] ?
result.push( arr1.shift() ) :
result.push( arr2.shift() ) ;
}
};
if(a.length < 2){
return a;
}
var arr1 = a.slice(0, Math.floor(a.length / 2));
var arr2 = a.slice(Math.floor(a.length / 2));
return merge( mergeSort(arr1), mergeSort(arr2));
};
var body = document.getElementsByTagName('body')[0];
var log = function(s){
var p = document.createElement('p');
var ps = document.getElementsByTagName('p');
p.innerHTML = s;
ps.length ?
body.insertBefore(p, ps[0]) :
body.appendChild(p);
//document.write(s + '<br />'); 破坏文档结构
//firefox下使用console.log并开启firebug会影响执行
}
function exeTest( callback ){
function test(){
var cost,
startTime,
arr = [];
testCount--;
// 构建随机数组
for(i=0;i<count;i++){
arr.push( Math.round(Math.random() * count) ); // 0 - count
}
startTime = + new Date();
arr = mergeSort(arr);
exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数
log('本次测试花费 '+ cost +' 毫秒, 还剩 '+ testCount +' 次测试');
if(testCount == 0 && typeof callback == 'function'){
callback();
}else{
// 预防浏览器挂起
setTimeout(test, 0);
}
}
test();
}
function callback(){
var sum = 0;
var result = '数组里有'+ count +'个随机数, 执行'+ num +'次后花费的毫秒数' + '<br />' +
'最大毫秒数为' + Math.max.apply(null, exeTimeArr) + '<br />' +
'最小毫秒数为' + Math.min.apply(null, exeTimeArr) + '<br />';
exeTimeArr.forEach(function(value) {
sum += value;
})
result += '平均毫秒数为' + Math.round( sum / num ) ;
log(result);
}
// 开始测试
exeTest(callback);
</script>
</body>
</html>
