_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
/
function radixSort(intArr) {
var cpy = new Int32Array(intArr.length);
var c4 = [].concat(_radixSort_0);
var c3 = [].concat(_radixSort_0);
var c2 = [].concat(_radixSort_0);
var c1 = [].concat(_radixSort_0);
var o4 = 0; var t4;
var o3 = 0; var t3;
var o2 = 0; var t2;
var o1 = 0; var t1;
var x;
for(x=0; x> 8) & 0xFF;
t2 = (intArr[x] >> 16) & 0xFF;
t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
c4[t4];
c3[t3];
c2[t2];
c1[t1];
}
for (x=0; x<256; x) {
t4 = o4 + c4[x];
t3 = o3 + c3[x];
t2 = o2 + c2[x];
t1 = o1 + c1[x];
c4[x] = o4;
c3[x] = o3;
c2[x] = o2;
c1[x] = o1;
o4 = t4;
o3 = t3;
o2 = t2;
o1 = t1;
}
for(x=0; x> 8) & 0xFF;
intArr[c3[t3]] = cpy[x];
c3[t3];
}
for(x=0; x> 16) & 0xFF;
cpy[c2[t2]] = intArr[x];
c2[t2];
}
for(x=0; x> 24) & 0xFF ^ 0x80;
intArr[c1[t1]] = cpy[x];
c1[t1];
}
return intArr;
}

编辑：

到目前为止，发现的最好/唯一的主要优化是JS类型的数组。将类型化数组用于普通基数排序的阴影数组可产生最佳效果。我还可以使用堆栈推入/弹出内置的JS从现场快速排序中挤出一些额外的东西。

最新的jsfiddle基准

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSort(intArr): 172 ms
radixSortIP(intArr): 1738 ms
quickSortIP(arr): 661 ms
200k
radixSort(intArr): 18 ms
radixSortIP(intArr): 26 ms
quickSortIP(arr): 58 ms

看来标准基数排序确实是此工作流程的主要选择。 如果有人有时间尝试进行循环展开或其他修改，我将不胜感激。

我有一个特定的用例，我想要JavaScript中最快的排序实现。客户端脚本将访问大型（50,000-2mil），未排序（基本上是随机的），整数（32位带符号）数组，然后需要对该数组进行排序和显示。

我已经实现了相当快的就地基数排序和就地快速排序jsfiddle基准，但是对于我的上限数组长度，它们仍然相当慢。快速排序在我的上限数组大小上表现更好，而基数排序在我的下限数组上表现更好。

defaultSort is the built-in JavaScript array.sort with an integer compare function

Intel C2Q 9650, 4GB, FireFox 3.6
2mil
radixSortIP(intArr): 5554 ms
quickSortIP(arr): 1796 ms
200k
radixSortIP(intArr): 139 ms
quickSortIP(arr): 190 ms
defaultSort(intArr): 354 ms

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSortIP(intArr): 990 ms
quickSortIP(arr): 882 ms
defaultSort(intArr): 3632 ms
200k
radixSortIP(intArr): 28 ms
quickSortIP(arr): 68 ms
defaultSort(intArr): 306 ms

问题

• 是否有可以满足我的用例/需求的排序算法的更好实现？
• 是否可以对本地基数/快速排序实现进行任何优化以提高性能？
• • 有没有一种有效的方法可以将我的基数排序从递归函数转换为迭代函数？内存和执行速度。

目标

• 我希望这些答案可以帮助我在基准测试中将性能提高20-30％。

澄清/注意事项

• “ DEFINE FAST”我更喜欢在所有现代浏览器上都能很好运行的一般情况，但是如果存在针对浏览器的优化，则可以进行重大改进。
• 排序可以在服务器端完成，但是我更希望避免这种情况，因为JS应用程序可能会变成独立的（与一些将传感器数据流传输到文件的现成的专有应用程序配对）。
• JavaScript可能不是最好的语言，但这是必需的。
• 我尝试将多个浏览器窗口实例用作临时多线程处理；它没有成功。我会对有关产生多个并发窗口的有用信息感兴趣。