Javascript Shell排序实现比合并排序更快
我得到了两个算法的实现:一个是shell排序，另一个是合并排序。Shell排序复杂度接近n^1.5，合并排序接近n* logn，因此基本上合并排序应该更快。然而，在我的测试中，我看到了不同的结果: shell排序比合并排序快得多。我相信我做错了什么，但没有看到这一点。
Shell排序工具：
var shell_sort = function(array){
var length = array.length;
var h = 1;
while( h < length / 3){
h = 3 * h + 1;
}
while( h > 0 ){
for ( var i = h; i < length; i++){
for ( var j = i; j > 0 && array[j] < array[j-h]; j-=h){
array.swap(j, j-h);
}
}
//decreasing h
h = --h / 3
}
return array;
};并合并排序：
var merge_sort = function(array){
function merge(left, right){
var result = [];
var il = 0;
var ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
if ( il < left.length){
result.push.apply(result,left.slice(il));
}
if (ir < right.length){
result.push.apply(result,right.slice(ir));
}
return result;
}
function merge_sort(items){
//well it is only 1 element
if (items.length < 2){
return items;
}
var middle = Math.floor(items.length / 2);
//create two arrays
var left = items.slice(0, middle);
var right = items.slice(middle);
return merge(merge_sort(left), merge_sort(right));
}
return merge_sort(array);
};下一个基本结果是由1,000万个元素组成的数组：
外壳排序: 12725ms
合并排序:34338 Merge
测试非常简单：
//sorting 100000 elements
array.generate_numbers(10000000);
console.time('10000000elements');
sort_algs(array);
console.timeEnd('10000000elements');其中，generate_numbers是一个简单的助手函数，它生成具有配置大小的数字数组，以及交换是一个更改元素位置的函数。
回答 4
Stack Overflow用户
发布于 2015-04-14 23:37:22
如果有人感兴趣，请找出没有这么多数组的algo源：
var merge_sort = function(array){
function merge(a, aux, lo, mid, hi ){
for (var k = lo; k <= hi; k++){
aux[k] = a[k];
}
debugger;
var i = lo;
var j = mid + 1;
for (var k = lo; k <= hi; k++){
if ( i > mid) a[k] = aux[j++];
else if ( j > hi ) a[k] = aux[i++];
else if ( aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
function sort(array, aux, lo, hi){
if (hi <= lo) return;
var mid = Math.floor(lo + (hi - lo) / 2);
sort(array, aux, lo, mid);
sort(array, aux, mid + 1, hi);
merge(array, aux, lo, mid, hi);
}
function merge_sort(array){
var aux = array.slice(0);
sort(array, aux, 0, array.length - 1);
return array;
}
return merge_sort(array);
};Stack Overflow用户
发布于 2015-04-07 21:56:10
在较高级别上，shell排序实现主要依赖于对swap()的调用，而合并排序涉及许多数组访问和操作。很简单，在shell排序和解释语言中，内置函数处理的逻辑与脚本的比率要高得多，这通常会导致更快的执行。
在特定情况下，合并排序将在每次调用merge()时创建一个新数组，在该数组上多次调用.push()，并最终在合并时丢弃该数组。shell排序完成了所有的工作，从来不需要创建或销毁数组。因此，相对于shell排序，合并排序的性能将受到浏览器使用的垃圾收集特性的严重影响。
如果我没记错的话，传统的合并排序分析假设创建、扩展和销毁数组都是大致恒定的时间操作。在Javascript中，情况可能不是这样。
Stack Overflow用户
发布于 2015-04-14 14:01:28
您可以看到Sedgewick的合并排序实现：http://algs4.cs.princeton.edu/22mergesort/Merge.java.html --他使用输入数组的副本来维护merge_sort函数中的小数组，因此他在创建数组和将元素推送到它方面没有任何开销。
https://stackoverflow.com/questions/29501448
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号